Question

Eigendecomposition

Eigenvectors and Eigenvalues

First recall that an eigenvector of a matrix \(A\) is a non-zero vector \(v\) such that

\[Av = \lambda v\]

for some scalar \(\lambda\)

The value \(\lambda\) is called an eigenvalue of \(A\).

If an \(n\times n\) matrix \(A\) has \(n\) linearly independent eigenvectors, then \(A\) may be decomposed in the following manner:

\[A = B\Lambda B^{-1}\]

where \(\Lambda\) is a diagonal matrix whose diagonal entries are the eigenvalues of \(A\) and the columns of \(B\) are the corresponding eigenvectors of \(A\).

Facts:

• An \(n\times n\) matrix is diagonizable \(\iff\) it has \(n\) linearly independent eigenvectors.
• A symmetric, positive definite matrix has only positive eigenvalues and its eigendecomposition \[A=B\Lambda B^{-1}\]

is via an orthogonal transformation \(B\). (I.e. its eigenvectors are an orthonormal set)

Calculating Eigenvalues

It is easy to see from the definition that if \(v\) is an eigenvector of an \(n\times n\) matrix \(A\) with eigenvalue \(\lambda\), then

\[Av - \lambda I = \bf{0}\]

where \(I\) is the identity matrix of dimension \(n\) and \(\bf{0}\) is an n-dimensional zero vector. Therefore, the eigenvalues of \(A\) satisfy:

\[\det\left(A-\lambda I\right)=0\]

The left-hand side above is a polynomial in \(\lambda\), and is called the characteristic polynomial of \(A\). Thus, to find the eigenvalues of \(A\), we find the roots of the characteristic polynomial.

Computationally, however, computing the characteristic polynomial and then solving for the roots is prohibitively expensive. Therefore, in practice, numerical methods are used - both to find eigenvalues and their corresponding eigenvectors. We won’t go into the specifics of the algorithms used to calculate eigenvalues, but here is a numpy example:

A = np.array([[0,1,1],[2,1,0],[3,4,5]])

u, V = la.eig(A)
print(np.dot(V,np.dot(np.diag(u), la.inv(V))))
print(u)

[[-0.+0.j  1.+0.j  1.+0.j]
 [ 2.+0.j  1.+0.j  0.+0.j]
 [ 3.+0.j  4.+0.j  5.+0.j]]
[ 5.8541+0.j -0.8541+0.j  1.0000+0.j]

NB: Many matrices are not diagonizable, and many have complex eigenvalues (even if all entries are real).

A = np.array([[0,1],[-1,0]])
print(A)

u, V = la.eig(A)
print(np.dot(V,np.dot(np.diag(u), la.inv(V))))
print(u)

[[ 0  1]
 [-1  0]]
[[ 0.+0.j  1.+0.j]
 [-1.+0.j  0.+0.j]]
[ 0.+1.j  0.-1.j]

# If you know the eigenvalues must be reeal
# because A is a positive definite (e.g. covariance) matrix
# use real_if_close

A = np.array([[0,1,1],[2,1,0],[3,4,5]])
u, V = la.eig(A)
print(u)
print np.real_if_close(u)

[ 5.8541+0.j -0.8541+0.j  1.0000+0.j]
[ 5.8541 -0.8541  1.    ]

Singular Values

For any \(m\times n\) matrix \(A\), we define its singular values to be the square root of the eigenvalues of \(A^TA\). These are well-defined as \(A^TA\) is always symmetric, positive-definite, so its eigenvalues are real and positive. Singular values are important properties of a matrix. Geometrically, a matrix \(A\) maps the unit sphere in \(\mathbb{R}^n\) to an ellipse. The singular values are the lengths of the semi-axes.

Singular values also provide a measure of the stabilty of a matrix. We’ll revisit this in the end of the lecture.

QR decompositon

As with the previous decompositions, \(QR\) decomposition is a method to write a matrix \(A\) as the product of two matrices of simpler form. In this case, we want:

\[A= QR\]

where \(Q\) is an \(m\times n\) matrix with \(Q Q^T = I\) (i.e. \(Q\) is orthogonal) and \(R\) is an \(n\times n\) upper-triangular matrix.

This is really just the matrix form of the Gram-Schmidt orthogonalization of the columns of \(A\). The G-S algorithm itself is unstable, so various other methods have been developed to compute the QR decomposition. We won’t cover those in detail as they are a bit beyond our scope.

The first \(k\) columns of \(Q\) are an orthonormal basis for the column space of the first \(k\) columns of \(A\).

Iterative QR decomposition is often used in the computation of eigenvalues.