ECE 602 Fall 2010

Quadratic Forms and the Kronecker Product

by

Stanislaw H. Żak

September 28, 2010

Quadratic Forms

A real quadratic form is the product x^{⊤}Qx, where Q is a specified n × n matrix with real coefficients and x is an n × 1 real, column, vector. Without loss of generality, the matrix Q can be taken to be symmetric, that is, Q = Q^{⊤}. Indeed, if Q is not symmetric, we can always replace it with a symmetric matrix without changing the quadratic form values. Indeed, because z = x^{⊤}Qx is a scalar, hence z^{⊤} = z, and we have

(x^{⊤}Qx)^{⊤} = x^{⊤}Q^{⊤}x = x^{⊤}Qx.

Therefore, we can write

x^{⊤}Qx = x^{⊤} (\frac{1}{2}Q + \frac{1}{2}Q^{⊤}) x = x^{⊤} (\frac{Q + Q^{⊤}}{2} ) x,

where \frac{1}{2} (Q + Q^{⊤}) is a symmetric matrix. Thus, the quadratic form values are unchanged if Q is replaced with the symmetric matrix \frac{1}{2} (Q + Q^{⊤}). From now on, in our study of quadratic forms, we assume that Q is symmetric.

A quadratic form x^{⊤}Qx, or equivalently, the matrix Q, is called positive semi-definite if x^{⊤}Qx ≥ 0 for all x. It is positive definite if x^{⊤}Qx > 0 for all x ≠ 0. If Q is positive semi-definite, then we write Q ≥ 0, if it is positive definite, we write Q > 0. We write Q_{1} ≥ Q_{2} to mean that Q_{1} − Q_{2} ≥ 0. We say that Q is negative semi-definite if x^{⊤}Qx ≤ 0 for all x, it is negative definite if x^{⊤}Qx < 0 for all x ≠ 0. Note that Q ≤ 0 if and only if −Q ≥ 0.

We now present tests for definiteness properties of symmetric matrices. We state these tests in terms of principal minors of a given real, symmetric, n × n matrix Q with elements q_{ij}. We will also give tests for definiteness in terms of eigenvalues of Q. The principal minors of Q are det Q itself and the determinants of submatrices of Q obtained by removing successively an i-th row and i-th column. Specifically, for p = 1, 2, …, n, the principal minors are

Δ_{p} ( \begin{matrix}i_{1}, & i_{2}, & …, & i_{p} \\ i_{1}, & i_{2}, & …, & i_{p} \end{matrix} ) = det [ \begin{matrix}q_{i_{1}i_{1}} & q_{i_{1}i_{2}} & ⋯ & q_{i_{1}i_{p}} \\ q_{i_{2}i_{1}} & q_{i_{2}i_{2}} & ⋯ & q_{i_{2}i_{p}} \\ ⋮ & ⋮ & ... & ⋮ \\ q_{i_{p}i_{1}} & q_{i_{p}i_{2}} & ⋯ & q_{i_{p}i_{p}} \end{matrix} ] 1 ≤ i_{1} < i_{2} < ⋯ < i_{p} ≤ n.

The above are called the principal minors of order p.

In the following, we use the fact that if Q = Q^{⊤}, then its eigenvalues are all real.

Theorem 1 The following are equivalent:

(i) The symmetric matrix Q is positive semi-definite.

(ii) Principal minors of Q are nonnegative, that is, for p = 1, 2, …, n,

Δ_{p} ( \begin{matrix}i_{1}, & i_{2}, & …, & i_{p} \\ i_{1}, & i_{2}, & …, & i_{p} \end{matrix} ) ≥ 0, 1 ≤ i_{1} < i_{2} < ⋯ < i_{p} ≤ n.

(iii) Eigenvalues of Q are nonnegative,

λ_{i}(Q) ≥ 0, i = 1, 2, …, n.

We now give two tests for Q = Q^{⊤} to be positive definite; one in terms of its leading principal minors, and the other in terms of its eigenvalues. The leading principal minors of Q are

Δ_{1} ( \begin{matrix}1 \\ 1 \end{matrix} ) = q_{11}, Δ_{2} ( \begin{matrix}1, & 2 \\ 1, & 2 \end{matrix} ) = det [ \begin{matrix}q_{11} & q_{12} \\ q_{21} & q_{22} \end{matrix} ] ,

Δ_{3} ( \begin{matrix}1, & 2, & 3 \\ 1, & 2, & 3 \end{matrix} ) = det [ \begin{matrix}q_{11} & q_{12} & q_{13} \\ q_{21} & q_{22} & q_{23} \\ q_{31} & q_{32} & q_{33} \end{matrix} ] , …, Δ_{n} ( \begin{matrix}1, & 2, & …, & n \\ 1, & 2, & …, & n \end{matrix} ) = det Q.

Theorem 2 The following are equivalent:

(i) The symmetric matrix Q is positive definite.

(ii) Leading principal minors of Q are positive, that is,

Δ_{p} ( \begin{matrix}1, & 2, & …, & p \\ 1, & 2, & …, & p \end{matrix} ) > 0, p = 1, 2, …, n.

(iii) Eigenvalues of Q are positive,

λ_{i}(Q) > 0, i = 1, 2, …, n.

If a given matrix Q ∈ ℝ^{n×n} is symmetric, then its eigenvalues are all real and there exists a unitary matrix U such that

U^{⊤}QU = [ \begin{matrix}λ_{1} & 0 & ⋯ & 0 \\ 0 & λ_{2} & ⋯ & 0 \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{n} \end{matrix} ] = Λ.  (1)

Using the above, one can show that a symmetric positive semi-definite matrix Q has a positive semi-definite symmetric square root, denoted Q^{1/2} or \sqrt{Q}, that satisfies

Q^{1/2}Q^{1/2} = Q.  (2)

Indeed, it follows from Theorem 1 that if Q = Q^{⊤} ≥ 0 then its eigenvalues are all nonnegative. Hence,

Λ^{1/2} = [ \begin{matrix}λ_{1}^{1/2} & 0 & ⋯ & 0 \\ 0 & λ_{2}^{1/2} & ⋯ & 0 \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{n}^{1/2} \end{matrix} ]  (3)

is well defined. Using the fact that U^{⊤}U = I_{n}, we can define

Q^{1/2} = UΛ^{1/2}U^{⊤},  (4)

which has the desired properties.

If Q = Q^{⊤} is positive semi-definite, and not positive definite, then some of its eigenvalues are equal to zero. Suppose that Q has r nonzero eigenvalues. Then, there is a unitary matrix, say U, such that

U^{⊤}QU = [ \begin{matrix}λ_{1} & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & λ_{2} & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & & ... & ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{r} & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & & & & & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \end{matrix} ] .  (5)

Let V ∈ ℝ^{n×r} be a matrix that consists of the first r columns of the matrix U, and let

C = [ \begin{matrix}λ_{1}^{1/2} & 0 & ⋯ & 0 \\ 0 & λ_{2}^{1/2} & ⋯ & 0 \\ ⋮ & & ... & ⋮ \\ 0 & 0 & ⋯ & λ_{r}^{1/2} \end{matrix} ] V^{⊤}.  (6)

Note that the matrix C is of full rank. We have

Q = C^{⊤}C.  (7)

We refer to (7) as a full rank factorization of Q because C is of full rank.

The Kronecker Product

Let A be an m × n and B be a p × q matrices. The Kronecker product of A and B, denoted A ⊗ B, is an mp × nq matrix defined by

A ⊗ B = [ \begin{matrix}a_{11}B & a_{12}B & ⋯ & a_{1n}B \\ a_{21}B & a_{22}B & ⋯ & a_{2n}B \\ ⋮ & ⋮ & ... & ⋮ \\ a_{m1}B & a_{m2}B & ⋯ & a_{mn}B \end{matrix} ] .  (8)

Thus, the matrix A⊗B consists of mn blocks. Using the definition of the Kronecker product, we can verify the following two properties:

(A ⊗ B) (C ⊗ D) = AC ⊗ BD,  (9)
(A ⊗ B)^{⊤} = A^{⊤} ⊗ B^{⊤}.  (10)

Let

X = [ x_{1}, x_{2}, …, x_{m} ]

be a n × m matrix, where x_{i}, i = 1, 2, …, m are the columns of X. Each x_{i} consists of n elements. Then, the vectorization operator or stacking operator is defined as

vec(X) = [ x_{1}^{⊤}, x_{2}^{⊤}, …, x_{m}^{⊤} ]^{⊤}
= [ x_{11} x_{21} ⋯ x_{n1} x_{12} x_{22} ⋯ x_{n2} ⋯ x_{1m} x_{2m} ⋯ x_{nm} ]^{⊤} (11)

is the column nm-vector formed from the columns of X taken in order. Let now A be an n × n, and C and X be n × m matrices. Then, the matrix equation

AX = C  (12)

can be written as

(I_{m} ⊗ A) vec(X) = vec(C).  (13)

Let B be an m × m matrix, then the matrix equation

XB = C  (14)

can be written as

(B^{⊤} ⊗ I_{n}) vec(X) = vec(C).  (15)

Using the above two facts, we can verify that the Sylvester matrix equation,

AX + XB = C,  (16)

where A is n × n, B is m × m, and C is n × m, can be written as

(I_{m} ⊗ A + B^{⊤} ⊗ I_{n}) vec(X) = vec(C).  (17)

Let λ_{i}, v_{i} be the eigenvalues and eigenvectors, respectively of A, and μ_{j} and w_{j} the eigenvalues and eigenvectors of m × m matrix B. Then,

(A ⊗ B) (v_{i} ⊗ w_{j}) = Av_{i} ⊗ Bw_{j}
= λ_{i}v_{i} ⊗ μ_{j}w_{j}
= λ_{i}μ_{j} (v_{i} ⊗ w_{j}) .  (18)

Thus, the eigenvalues of A ⊗ B are λ_{i}μ_{j}, and their respective eigenvectors are v_{i} ⊗ w_{j} for i = 1, 2, …, n, j = 1, 2, …, m.

We use the above result to study the matrix equation given by (16). We represent (16) as

M vec(X) = vec(C),  (19)

where

M = I_{m} ⊗ A + B^{⊤} ⊗ I_{n}.  (20)

The solution to (19) is unique if, and only if, the mn × mn matrix M is nonsingular. To find the condition for this to hold, consider the following matrix

(I_{m} + εB^{⊤}) ⊗ (I_{n} + εA) = I_{m} ⊗ I_{n} + εM + ε^{2}B^{⊤} ⊗ A  (21)

whose eigenvalues are

(1 + εμ_{j}) (1 + ελ_{i}) = 1 + ε (μ_{j} + λ_{i}) + ε^{2}μ_{j}λ_{i}  (22)

because for a square matrix Q,

λ_{i} (I_{n} + εQ) = 1 + ελ_{i} (Q) .

Comparing terms in ε in (21) and (22), we conclude that the eigenvalues of M are λ_{i} + μ_{j}, i = 1, 2, …, n, j = 1, 2, …, m. Hence, M is nonsingular if and only if

λ_{i} + μ_{j} ≠ 0.  (23)

The above is the necessary and sufficient condition for the solution X of the matrix equation AX + XB = C to be unique.

Another useful identity involving the Kronecker product is

vec(ABC) = (C^{⊤} ⊗ A) vec(B)  (24)

For further information on the subject of the Kronecker product, we refer the reader to Brewer [1].

References

[1] J. W. Brewer. Kronecker products and matrix calculus in system theory. IEEE Transactions on Circuits and Systems, CAS-25(9):772–781, September 1978.