Matrix Equations

Go to: Introduction, Notation, Index

In all the equations below, x, y, z, X, Y and Z are the unknown vectors or matrices.

Conic Equation

A conic, or conic section, is the locus of points satisfying the quadratic equation [x; 1]^TS[x; 1]=0 where x_[2#1] is a 2-dimentional real vector and S_[3#3] is a real symmetric matrix; all non-zero multiples of S result in the same conic.

The conic equation can be classified as one of the following cases (where k is an arbitrary multiple):

Discrete-time Lyapunov Equation

The discrete-time Lyapunov equation is AXA^H - X + Q = 0 where Q is hermitian. This is a special case of the Stein equation.

• There is a unique solution X iff (eig(A)eig(A)^H - 1) has no zero elements, i.e. iff no eigenvalue of A is the reciprocal of an eigenvalue of A^H. If this condition is satisfied, the unique X is Hermitian.
• If A is convergent then X is unique and Hermitian and X=SUM(A^kQB^k,k=0..infinity) where B=A^H.
• If A is convergent and Q is positive definite (or semi-definite) then X is unique, Hermitian and positive definite (or semi-definite).

The equivalent equation for continuous-time systems is the Lyapunov equation.

Discrete Riccati Equation

The discrete Riccati equation is the quadratic equation [A, X: n#n; B: n#m; C: m#n; R, Q: hermitian] X = A^HXA - (C+B^HXA)^H(R+B^HXB)^-1(C+B^HXA) + Q

Quadratic Form Optimization

Suppose H_[n#n]=UDU^H is hermitian, U is unitary and D=diag(d)=diag(eig(H)) contains the eigenvalues (which are necessarily real) in decreasing order. Then the corresponding quadratic form is the real-valued expression x^HHx.

• Rayleigh-Ritz Theorem: the value of the ratio x^HHx(x^Hx)^-1 lies within the closed interval [d_n, d₁] that is bounded by the smallest and largest eigenvalues of H. Specifically
  • min_x (x^HHx | x^Hx=1) = min_x (x^HHx(x^Hx)^-1 | x≠0) = d_n and this bound is attained by the corresponding eigenvector, x=u_n [4.8]
  • max_x (x^HHx | x^Hx=1) = max_x (x^HHx(x^Hx)^-1 | x≠0) = d₁ and this bound is attained by the corresponding eigenvector, x=u₁ [4.8]

• Courant-Fischer Theorem: We can extend the Rayleigh-Ritz theorem to find the k-dimensional subspace, W_[n#n-k]^Hx=0 , in which the the peak value of the ratio x^HHx(x^Hx)^-1 is as small as possible. Specifically
  • min_W max_x (x^HHx | x^Hx=1 and W_[n#n-k]^Hx=0) = min_W max_x (x^HHx(x^Hx)^-1 |  x≠0 and W_[n#n-k]^Hx=0)  =  d_k and this bound is attained by W=U_:,k+1:n and x=u_k  [4.7].
  • max_W min_x (x^HHx | x^Hx=1 and W_[n#n-k]^Hx=0) = max_W min_x (x^HHx(x^Hx)^-1 |  x≠0 and W_[n#n-k]^Hx=0)  =  d_n-k+1 and this bound is attained by W=U_:,1:n-k and x=u_n-k+1 .

• We can generalize the Rayleigh-Ritz theorem to a matrix argument, X, in either of two ways which, surprisingly, turn out to be equivalent. If S is +ve definite Hermitian and H is Hermitian, then
  • max_X tr((X^HSX)^-1 X^HHX) | rank(X_[n#k])=k) = sum(d_1:k) [4.11]
  • max_X det((X^HSX)^-1 X^HHX) | rank(X_[n#k])=k) = prod(d_1:k) [4.12]

where d are the eigenvalues of S^-1H sorted into decreasing order and these bounds are attained by taking the columns of X to be the corresponding eigenvectors.

Linear Discriminant Analysis (LDA): If vectors x are randomly generated from a number of classes with H the covariance of the class means and S the average covariance within each class, then tr((X^HSX)^-1 X^HHX) and det((X^HSX)^-1 X^HHX) are two alternative measures of class separability. We can find a dimension-reducing transformation that maximizes separability by taking y = P^Tx where the columns of P_[k#n] are the eigenvectors of S^-1H corresponding to the k largest eigenvalues. This choice maximizes both separability measures for any given k.

• If S is +ve definite Hermitian and H is Hermitian and A_[n#m] is a given matrix, then  max_X tr(([A X]^HS[A X])^-1 [A X]^HH[A X] | rank([A X_[n#k]])=m+k) = tr((A^HSA)^-1A^HHA) + sum(d_1:k) where d are
  1.  the eigenvalues of (I-A(A^HSA)^-1A^HS)S^-1H sorted into decreasing order and this maximum may be attained by taking the columns of X to be the corresponding eigenvectors  [4.13].
  2. the eigenvalues of V^HC^-HHC^-1V sorted into decreasing order where S=C^HC is the Cholesky decomposition and the columns of V are an orthonormal basis for the null space of A^HC^H. This maximum may be attained by taking the columns of X to be the corresponding eigenvectors pre-multiplied by C^-1V [4.14].
• If S is +ve definite Hermitian and H is Hermitian and A_[n#m] is a given matrix, then  max_X det(([A X]^HS[A X])^-1 [A X]^HH[A X] | rank([A X_[n#k]])=m+k) = det((A^HSA)^-1A^HHA)×prod(l_1:k) where l are the eigenvalues of  S^-1H(I  - A (A^HHA)^-1A^HH  ) sorted into decreasing order and this maximum may be attained by taking the columns of X to be the corresponding eigenvectors. [4.15]

Linearly Constrained Quadratic Form Minimization

• If x is real and H is positive-definite real-symmetric, we can use a Lagrange multiplier to minimize x^THx subject to the real-valued constraint A^Tx=c to obtain x = H^-1A(A^TH^-1A)^-1c provided that both H and A^TH^-1A are non-singular. For the special case, H=I, this becomes x=A(A^TA)^-1c = (A⁺)^Tc where A⁺ is the pseudoinverse.
• If x is complex and H is positive-definite Hermitian, we can use a complex Lagrange multiplier to minimize x^HHx subject to the complex-valued constraint A^Hx+B^Tx^C=c to obtain x=H^-1[A B][U V; V^H U^T]^-1[c; c^C] provided that both H and [U V; V^H U^T] are non-singular where U=A^HH^-1A+(B^HH^-1B)^T is Hermitian and V=A^HH^-1B+(A^HH^-1B)^T is symmetric.

Linear Equation

A linear equation has the form Ax - b = 0.

Exact Solution

• [A_m#n] The linear equation has a unique exact solution iff rank([A b]) = rank([A]) = n. The solution is x = A^-1b.
• [A_m#n] The linear equation has infinitely many exact solutions iff rank([A b]) = rank([A]) < n.
  • The complete set of solutions is x = x₀+y where x₀ is any solution and y ranges over the null space of A.

Least Squares solutions

If there is no exact solution, we can find the x that minimizes d = ||Ax-b|| = (Ax - b)^H(Ax - b) .

• The x that minimizes d is given by x=A^#b where A^# is any generalized inverse of A.
• Of all the x that attain the minimum d, the one with least ||x|| is given by x=A⁺b where A⁺ is the pseudoinverse of A.
• [rank(A_m#n)=n] The unique x that minimizes d is given by x = (A^HA)^-1A^Hb. This x gives d = b^H(I_m#m-A(A^HA)^-1A^H)b.
  • d is zero iff rank([A b]) = n.

Recursive Least Squares

We can express the least squares solution to the augmented equation [A; U]y - [b; v] = 0 in terms of the least squares solution to Ax - b = 0.

[rank(A_m#n)=n] The least squares solution to the is y = x + K(v-Ux) where x is the least squares solution to Ax-b=0 and K = (A^HA)^-1U^H(I+U(A^HA)^-1U^H)^-1. The inverse of the augmented grammian is given by ([A; U]^H[A; U])^-1 = (A^HA)^-1-KU(A^HA)^-1. Thus finding the least squares solution of the augmented equation requires the inversion of a matrix, (I+U(A^HA)^-1U^H), whose dimension equals the number of rows of U instead of the number of rows of  [A; U]. The process is particularly simple if U has only one row. The computation may be reduced at the expense of numerical stability by calculating (A^HA)^-1U^H as (U(A^HA)^-1)^H.

Lyapunov Equation

The (continuous) Lyapunov equation is AX + XA^H + Q = 0 where Q is hermitian. This is a special case of the Sylvester equation.

• There is a unique solution for X iff no eigenvalue of A has a zero real part and no two eigenvalues are negative complex conjugates of each other. If this condition is satisfied then the unique X is hermitian.
• If A is stable then X is unique and Hermitian and equals INTEGRAL(EXP(At) Q EXP(A^Ht),t=0..infinity)
• If A is stable and Q is positive definite (or semi-definite) then X is unique, hermitian and positive definite (or semi-definite).

The equivalent equation for discrete-time systems is the Stein equation.

Riccati Equation

The (continuous) Riccati equation is the quadratic equation [A, X, C, D: n#n; C, D: hermitian] XDX + XA + A^HX - C = 0

Stein Equation

A Stein equation has the form AXB - X + Q = 0.

• There is a unique solution for X iff (eig(A)eig(B)^T - 1) has no zero elements, i.e. iff no eigenvalue of A is the reciprocal of an eigenvalue of B.
• AXB - X + Q = 0 is equivalent to the linear equation (I-KRON(B^T,A))x: = q: where x: and q: contain the concatenated columns of X and Q. This is a numerically poor way to determine X.
• The discrete-time lyapunov equation is a special case of the Stein equation with B=A^H and Q hermitian.

Sylvester Equation

The Sylvester equation is AX + XB + Q = 0

• There is a unique solution for X iff no eigenvalue of A is the negative of an eigenvalue of B.
• AX + XB + Q = 0 is equivalent to the linear equation (KRON(I, A)+KRON(B^T,I))x: = -q: where x: and q: contain the concatenated columns of X and Q. This is a numerically poor way to determine X.
• The lyapunov equation is a special case of the Sylvester equation with B=A^H and Q hermitian.