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.

Discrete-time Lyapunov Equation

The discrete-time Lyapunov equation is AXAH - 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 AH. If this condition is satisfied, the unique X is Hermitian.
• If A is convergent then X is unique and Hermitian and X=SUM(AkQBk,k=0..infinity) where B=AH.
• 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 = AHXA - (C+BHXA)H(R+BHXB)-1(C+BHXA) + Q

Suppose H[n#n]=UDUH is hermitian, U is unitary and D=diag(d)=diag(eig(H)) contains the eigenvalues in decreasing order. Then the corresponding quadratic form is the real-valued expression xHHx.

• Courant-Fischer Theorem: minW maxx (xHHx | xHx=1 and W[n#k]Hx=0) = minW maxx (xHHx(xHx)-1W[n#k]Hx=0)  =  dn-k and this bound is attained by W=U:,n-k+1:n and y=un-k  [4.7].
• Rayleigh-Ritz Theorem: maxx (xHHx | xHx=1) = maxx (xHHx(xHx)-1 | x!=0) = d1 and  minx (xHHx | xHx=1) = minx (xHHx(xHx)-1 | x!=0) = dn and these bounds are attained by x=u1 and y=un respectively [4.8].

We can generalize the Rayleigh-Ritz theorem to multiple dimensions in either of two ways which surprisingly turn out to be equivalent. If W is +ve definite Hermitian and B is Hermitian, then

• maxX tr((XHWX)-1 XHBX | rank(X[n#k])=k) = sum(d1:k) [4.11]
• maxX det((XHWX)-1 XHBX | rank(X[n#k])=k) = prod(d1:k) [4.12]
where d are the eigenvalues of W-1B 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 B the covariance of the class means and W the average covariance within each class, then tr((XHWX)-1 XHBX) and det((XHWX)-1 XHBX) are two alternative measures of class separability. We can find a dimension-reducing transformation that maximizes separability by taking y = ATx where the columns of A[k#n] are the eigenvectors of W-1B corresponding to the k largest eigenvalues. This choice maximizes both separability measures for any given k.

• If W is +ve definite Hermitian and B is Hermitian and A[n#m] is a given matrix, then  maxX tr(([A X]HW[A X])-1 [A X]HB[A X] | rank([A X[n#k]])=m+k) = tr((AHWA)-1AHBA) + sum(d1:k) where d are
1.  the eigenvalues of (I-A(AHWA)-1AHW)W-1B 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 VHF-HBF-1V sorted into decreasing order where W=FHF and the columns of V are an orthonormal basis for the null space of AHFH. This maximum may be attained by taking the columns of X to be the corresponding eigenvectors pre-multiplied by F-1V [4.14].
• If W is +ve definite Hermitian and B is Hermitian and A[n#m] is a given matrix, then  maxX det(([A X]HW[A X])-1 [A X]HB[A X] | rank([A X[n#k]])=m+k) = det((AHWA)-1AHBA)×prod(l1:k) where l are the eigenvalues of  W-1B(I  - A (AHBA)-1AH ) sorted into decreasing order and this maximum may be attained by taking the columns of X to be the corresponding eigenvectors. [4.15]

Linear Equation

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

Exact Solution

• [Am#n] The linear equation has a unique exact solution iff rank([A b]) = rank([A]) = n. The solution is x = A-1b.
• [Am#n] The linear equation has infinitely many exact solutions iff rank([A b]) = rank([A]) < n.
• The complete set of solutions is x = x0+y where x0 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(Am#n)=n] The unique x that minimizes d is given by x = (AHA)-1AHb. This x gives d = bH(Im#m-A(AHA)-1AH)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(Am#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 = (AHA)-1UH(I+U(AHA)-1UH)-1. The inverse of the augmented grammian is given by ([A; U]H[A; U])-1 = (AHA)-1-KU(AHA)-1. Thus finding the least squares solution of the augmented equation requires the inversion of a matrix, (I+U(AHA)-1UH), 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 (AHA)-1UH as (U(AHA)-1)H.

Lyapunov Equation

The (continuous) Lyapunov equation is AX + XAH + 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(AHt),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 + AHX - 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(BT,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=AH 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(BT,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=AH and Q hermitian.

This page is part of The Matrix Reference Manual. Copyright © 1998-2022 Mike Brookes, Imperial College, London, UK. See the file gfl.html for copying instructions. Please send any comments or suggestions to "mike.brookes" at "imperial.ac.uk".
Updated: \$Id: equation.html 11291 2021-01-05 18:26:10Z dmb \$