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. [4.18]

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.
  • If we include a Hermitian weight matrix, W, the x that minimizes d = (Ax - b)^HW(Ax - b) is  x = (A^HWA)^-1A^HWb. If W is taken as the inverse of the error-covariance matrix of an observation vector, b, then the expression gives the minimum variance unbiassed estimator of x.

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.