Matrix Reference Manual
Matrix Properties

Go to: Introduction, Notation, Index

Adjoint or Adjugate

The adjoint of A, ADJ(A) is the transpose of the matrix formed by taking the cofactor of each element of A.

• ADJ(A) A = det(A) I
  • If det(A) != 0, then A^-1 = ADJ(A) / det(A)

Characteristic Equation

[n#n] The characteristic equation of a matrix A is |tI-A| = 0. It is a polynomial equation in t.

The properties of the characteristic equation are described in the section on eigenvalues.

Characteristic Matrix

[n#n]: The characteristic matrix of A is (tI-A) and is a function of the scalar t.

The properties of the characteristic matrix are described in the section on eigenvalues.

Characteristic Polynomial

[n#n] The characteristic polynomial, p(t), of a matrix A is p(t) = |tI - A|.

The properties of the characteristic polynomial are described in the section on eigenvalues.

Cofactor

The cofactor of a minor of A:n#n is equal to the product of (a) the determinant of the submatrix consisting of all the rows and columns that are not in the minor and (b) -1 raised to the power of the sum of all the row and column indices that are in the minor.

The cofactor of the element a(i,j) equals -1^i+j det(B) where B is the matrix formed by deleting row i and column j from A.

See minor, adjoint

Conjugate Transpose

X=Y^H is the Hermitian transpose or Conjugate transpose of Y iff x(i,j)=conj(y(j,i)).

See Hermitian Transpose.

Determinant

For an n#n matrix A, det(A) is a scalar number defined by det(A)=sgn(PERM(n))'*prod(A(1:n,PERM(n)))

This is the sum of n! terms each involving the product of n matrix elements of which exactly one comes from each row and each column. Each term is multiplied by the signature (+1 or -1) of the column-order permutation . See the notation section for definitions of sgn(), prod() and PERM().

The determinant is important because INV(A) exists iff det(A) != 0.

Geometric Interpretation

The determinant of a matrix equals the +area of the +parallelogram that has the matrix columns as n of its sides. If a vector space is transformed by multiplying by a matrix A, then all +areas will be multiplied by det(A).

Properties of Determinants

• det(AB) = det(A) det(B)
• det(A^T) = det(A)
• det(A^H) = conj(det(A))
• det(cA) = cⁿ det(A)
• Interchanging any pair of columns of a matrix multiplies its determinant by -1(likewise rows).
• Multiplying any column of a matrix by c multiplies its determinant by c (likewise rows).
• Adding any multiple of one column onto another column leaves the determinant unaltered (likewise rows).
• det(A) != 0 iff INV(A) exists.
• [A,B:n#m ; m>=n]: If Q = CHOOSE(m,n). and d(k) = det(A(:,Q(k,:)) det(B(:,Q(k,:)) for k=1:rows(Q) then det(AB^T) = sum(d). This is the Binet-Cauchy theorem.
• Suppose that for some r, P = CHOOSE(n,r) and Q = CHOOSE(n,n-r) with the rows of Q ordered so that P(k,:) and Q(k,:) have no elements in common. If we define D(m,k) = (-1)^{sum([P(m,:) P(k,:)])} det(A(P(m,:)^T,P(k,:)) det(A(Q(m,:)^T,Q(k,:)) for m,k=1:rows(P) then det(A) = sum(D(m,:)) = sum(D(:,k)) for any k or m. This is the Laplace expansion theorem.
• • If we set k=r=1 then P(m,:)=[m] and we obtain the familiar expansion by the first column:
    d(m)=(-1)^m+1 A(m,1) det(A([1:m-1 m+1:n]^T,2:n)) and det(A)=sum(d).
• det(A) = 0 iff the columns of A are linearly dependent (likewise rows).
• • det(A) = 0 if two columns are identical (likewise rows).
  • det(A) = 0 if any column consists entirely of zeros (likewise rows).

Determinants of simple matrices

• det([a b; c d]) = ad - bc
• The determinant of a diagonal or triangular matrix is the product of its diagonal elements.
• The determinant of an orthogonal matrix is 1.
• The determinant of a permutation matrix equals the signature of the column permutation.

Determinants of block matrices

• [B,C:m*n]: det([A, B; C^T, D]) = det([D, C^T; B, A]) = det(A)*det(D-C^TA^-1B) = det(D)*det(A-B^TD^-1A)

The quantity D-C^TA^-1B is called the Schur complement of A in [D, C^T; B, A].

• [B,C:m*n]: det([I, B; C^T, I]) = det(I-B^TC) = det(I-BC^T) = det(I-C^TB) = det(I-CB^T)
• [A:m*m, D:n*n]: det([A, B; 0, D]) = det(A)*det(D)
• [A,B,C: n*n]: det([A, B; C, 0]) = -det(BC')
• [A,B,C,D: n*n, CD=DC]: det([A, B; C, D]) = det(AD-BC)
• [A,B,C,D: n*n, AC=CA]: det([A, B; C, D]) = det(AD-CB)

• [A,B,C,D: n*n, CD=DC]: det([A, B; C, D]) = det(AD-BC)

• [A,B,C,D: n*n, AB=BA]: det([A, B; C, D]) = det(DA-CB)
• [A,B,C,D: n*n, BD=DB]: det([A, B; C, D]) = det(DA-BC)

Eigenvalues

The eigenvalues of A are the roots of its characteristic equation: |tI-A| = 0.

The properties of the eigenvalues are described in the section on eigenvalues.

Generalized Inverse

The generalized inverse of X:m#n is any matrix, X^#:n#m satisfying XX^#X=X. Note that if X is singular or non-square, then X^# is not unique.

• If X is square and non-singular, X^# is unique and equal to X^-1.
• (X^#)^H is a generalized inverse of X^H.
• [k!=0] X^#/k is a generalized inverse of kX.
• [A,B non-singular] B^-1X^#A^-1 is a generalized inverse of AXB
• rank(X^#) >= rank(X).
• rank(X)=rank(X^#) iff X is the generalized inverse of X^# ( i.e. X^#XX^#=X^#.).
• XX^# and X^#X are idempotent and have the same rank as X. XX^# is a projection onto the column space of X.
• • I-XX^# and I-X^#X are also idempotent.
• The value of x that minimizes ||Ax-b|| is given by x=A^#b. With this value of x, the error Ax-b is orthogonal to the columns of A. If we define the projection P=AA^#, then Ax=Pb and Ax-b=-(I-P)b.
• If X:m#n has rank r, we can find A:n#n-r, B:n#r and C:m#m-r whose columns form bases for the null space of X, the range of X⁺X and the null space of X^H respectively.
• • The set of generalized inverses of X is precisely given by X^#=X⁺+AY+BZC^H for arbitrary Y:n-r#m and Z:r#m-r.
  • For a given choice of A, B and C, each X^# corresponds to a unique Y and Z.
  • XX^# is hermitian iff Z=0.
• If X:m#n has rank r, we can find A:n#n-r, F:n#r and C:m#m-r whose columns form bases for the null space of X, the range of X⁺ and the null space of X^H respectively. We can also find G:m#r such that X⁺=FG^H.
• • The set of generalized inverses of X for which X is also the generalised inverse of X^# is precisely given by X^#=(F+AV)(G+CW)^H for arbitrary V:n-r#r and W:m-r#r.
  • For a given choice of A, C, F and G each X^# corresponds to a unique V and W.

See also: Pseudoinverse

Hermitian Transpose or Conjugate Transpose

X=Y^H is the Hermitian transpose or Conjugate transpose of Y iff x(i,j)=conj(y(j,i)).

Inverse

B is a left inverse of A if BA=I. B is a right inverse of A if AB=I.

If BA=AB=I then B is the inverse of A and we write B=A^-1.

• [A:n#n] AB=I iff BA=I, hence inverse, left inverse and right inverse are all equivalent for square matrices.
• (AB^-1)=B^-1A^-1
• [A:n#m, B:m#n] AB=I implies that n<=m and that rank(A)=rank(B)=n.
• [A:m#m, D:n#n] [A, B; C, D]^-1 = [X, -XBD^-1; -D^-1CX, D^-1(I+CXBD^-1)] where X =(A-BD^-1C)^-1

See also: Generalized Inverse, Pseudoinverse

Kernel

The kernel (or null space) of A is the subspace of vectors x for which Ax = 0. The dimension of this subspace is the nullity of A.

• The kernel of A is the orthogonal complement of the range of A^H

Linear Independence

The columns of A are linearly independent iff the only solution to Ax=0 is x=0.

• If the columns of A:m#n are linearly independent then m >= n

Matrix Norms

Euclidean or Frobenius Norm

The Euclidean or Frobenius norm of a matrix A equals sqrt(sum(ABS(A).²)) and is written ||A||_F. It is always a real number.

• ||A||_F = ||A^T||_F = ||A^H||_F
• ||A||_F² = tr(A^HA)
• [Q: orthogonal]: ||A||_F = ||QA||_F = ||AQ||_F

p-Norms

||A||_p = max(||Ax||_p) where the max() is taken over all x with ||x||_p = 1 where ||x||_p denotes the vector p-norm for p>=1.

• ||AB||_p <= ||A||_p ||B||_p
• ||Ax||_p <= ||A||_p ||x||_p
• [A:m#n]: ||A||₂ <= ||A||_F <= sqrt(n) ||A||₂
• [A:m#n]: max(ABS(A)) <= ||A||₂ <= sqrt(mn) max(ABS(A))
• ||A||₂ <= sqrt(||A||₁ ||A||_inf)
• ||A||₁ = max(sum(ABS(A')))
• ||A||_inf = max(sum(ABS(A)))
• [A:m#n]: ||A||_inf <= sqrt(n) ||A||₂ <= sqrt(mn) ||A||_inf
• [A:m#n]: ||A||₁ <= sqrt(m) ||A||₂ <= sqrt(mn) ||A||₁
• [Q: orthogonal]: ||A||₂ = ||QA||₂ = ||AQ||₂

Minor

A kth-order minor of A is the determinant of a k#k submatrix of A.

A principal minor is one whose diagonal elements lie on the principal diagonal of A.

Null Space

The null space (or kernel) of A is the subspace of vectors x for which Ax = 0. The dimension of this subspace is the nullity of A.

• The null space of A is the orthogonal complement of the range of A^H

Permanent

For an n#n matrix A, pet(A) is a scalar number defined by pet(A)=sum(prod(A(1:n,PERM(n))))

This is the same as the determinant except that the individual terms within the sum are not multiplied by the signatures of the column permutations.

Properties of Permanents

• pet(A.') = pet(A)
• pet(A') = conj(pet(A))
• pet(cA) = cⁿ pet(A)
• [P: permutation matrix]: pet(PA) = pet(AP) = pet(A)
• [D: diagonal matrix]: pet(DA) = pet(AD) = pet(A) pet(D) = pet(A) prod(diag(D))

Permanents of simple matrices

• pet([a b; c d]) = ad + bc
• The permanent of a diagonal or triangular matrix is the product of its diagonal elements.
• The permanent of a permutation matrix equals 1.

Pseudoinverse

The pseudoinverse (or Moore-Penrose pseudoinverse) of X is the unique matrix X⁺ that satisfies:

1. XX⁺X=X
2. X⁺XX⁺=X⁺
3. (XX⁺)^H=XX⁺
4. (X⁺X)^H=X⁺X

• The pseudoinverse of X is the generalized inverse having the lowest Frobenius norm.

Rank

The rank of A is the dimension of its range.

• rank(A) = rank(A^T) = rank(A^H)
• rank(A) = maximum number of linearly independent columns (or rows).
• [A:n#n]: rank(A) + nullity(A) = n
• [A:n#n]: A is non singular iff rank(A)=n.
• [A:m#n, B:n#k ]: rank(A) + rank(B) - n <= rank(AB) <= min(rank(A), rank(B))
• rank(A + B) <= rank(A) + rank(B)
• [X:m#m and Y:n#n non-singular]: rank(XA) = rank(AY) = rank(A)
• rank(KRON(A,B)) = rank(A)rank(B)
• rank(DIAG(A,B,...,Z)) = sum(rank(A), rank(B), ..., rank(Z))

Range

The range (or image) of A is the subspace of vectors that equal Ax for some x. The dimension of this subspace is the rank of A.

• [A:m#n] The range of A is the orthogonal complement of the null space of A^H.

Submatrix

A submatrix of A is a matrix formed by the elements a(i,j) where i ranges over a subset of the rows and j ranges over a subset of the columns.

Trace

The trace of a square matrix is the sum of its diagonal elements: tr(A)=sum(diag(A))

In the formulae below, the argument of tr() must always be square.

• tr(aA) = a * tr(A)
• tr(A^T) = tr(A)
• tr(A+B) = tr(A) + tr(B)
• tr(AB) = tr(BA)
  • tr((AB)^k) =tr((BA)^k)
• a^Tb = tr(ab^T)
• a^TXb = tr(Xba^T)
• tr(ab^H) = conj(a^Hb)
• tr(ABCD) = tr(BCDA) = tr(CDAB) = tr(DABC)
• Similar matrices have the same trace: tr(X^-1AX) = tr(A)
• tr(A^HB) = sum(A.*B)
  • tr(A^HA) = ||A||
• tr(KRON(A,B))=tr(A) tr(B)

Spectrum

The spectrum of A is the set of all its eigenvalues.

Transpose

X=Y^T is the transpose of Y iff x(i,j)=y(j,i).

Vector Norms

Euclidean Norm

The Euclidean norm of a vector x equals the square root of the sum of the squares of the absolute values of all its elements and is written ||x||. It is always a real number and corresponds to the normal notion of the vector's length.

• ||x||² = x^Hx = tr(xx^H)
• Cauchy-Schwartz inequality: |x^Hy| <= ||x|| ||y||
• [Q: orthogonal]: ||Qx|| = ||x||

Holder Norms or p-Norms

The p-norm of a vector x is defined by ||x||_p = sum(abs(x).^p)^(1/p) for p>=1. The most common values of p are 1, 2 and infinity.

• City-Block Norm: ||x||₁ = sum(abs(x))
• Euclidean Norm: ||x|| = ||x||₂ = sqrt(x'x)
• Infinity Norm: ||x||_inf = max(abs(x))
• Hölder inequality: |x'y| <= ||x||_p ||y||_q where 1/p + 1/q = 1
• ||x||_inf <= ||x||₂ <= ||x||₁ <= sqrt(n) ||x||₂ <= n ||x||_inf

The Matrix Reference Manual is written by Mike Brookes, Imperial College, London, UK. Please send any comments or suggestions to mike.brookes@ic.ac.uk