8.5. Diagonalization and Powers of A¶
Here, we will establish a factoring of a matrix based on its eigenvalues
and eigenvectors. This factoring is called both diagonalization and
eigen-decomposition. Then, we will use the factoring to find a
computationally efficient way to compute powers of the matrix
(). Then in Change of Basis and Difference Equations, we will extend
this to
, where
is a vector.
This final result has direct application to difference equations, which
are used to solve several types of problems.
8.5.1. Diagonalization¶
The eigenpairs of the matrix
give us
equations.
We wish to combine the equations into one matrix equation.
Consider the product of and a matrix called
containing the eigenvectors of
as the
columns.
The matrix is a diagonal eigenvalue matrix. If the
matrix has linearly independent eigenvectors, which will be the case
when all eigenvalues are different (no repeating
s),
then
is invertible.
This factoring of is called the diagonalization
factoring.
8.5.1.1. When does Diagonalization not work?¶
Notice that for the diagonalization factoring to work we need to find the inverse of the eigenvector matrix. So each eigenvector must be independent of the other eigenvectors.
One example of a matrix with repeating eigenvectors is a
matrix with the same values on the forward diagonal
and a zero on the backward diagonal. The determinant of the
characteristic matrix has repeating eigenvalues, so it will also have
repeating eigenvectors. Thus the eigenvector matrix is singular and may
not be inverted.
>> A = [5 7; 0 5]
A =
5 7
0 5
>> [X, L] = eig(A)
X =
1.0000 -1.0000
0 0.0000
L =
5 0
0 5
>> rank(X)
ans =
1
8.5.1.2. Diagonalization of a Symmetric Matrix¶
Symmetric matrices have a simplified diagonalization because the matrix
of eigenvectors of a symmetric matrix, , is orthogonal
(The Schur Decomposition of Symmetric Matrices). Recall also from
Matrix Transpose Properties that from the spectral theorem,
orthogonal matrices have the property
. Thus the diagonalization of a
symmetric matrix is shown below and is also called the spectral
decomposition of a symmetric matrix.
Note
Recall that the columns of orthonormal matrices must be unit vectors
(length of 1), which the eig
function returns. Orthonormal
columns are required to use a transposed matrix instead of the
inverse matrix.
8.5.2. Powers of A¶
How does one compute matrix raised to the power
(
)?
The brute force approach is to simply multiply
by itself
times. This could be slow if
and the size of the matrix (
) are large.
If
is a
square matrix, the product
requires
multiply and addition operations (
). Thus
has complexity of
; or if we are clever about the order of the multiplications, it could be reduced to
. That is:
Fortunately, diagonalization gives us a faster way to compute
as a stand-alone matrix. The complexity of this
method is
.
Because the matrix is diagonal, only the individual
values need be raised to the
power
(element-wise exponent).
Example Power of A
In this example, the matrix is symmetric, so the inverse simplifies to a transpose.
>> S = gallery('moler', 4)
S =
1 -1 -1 -1
-1 2 0 0
-1 0 3 1
-1 0 1 4
>> [Q, L] = eig(S)
Q =
-0.8550 0.1910 0.3406 -0.3412
-0.4348 -0.6421 -0.6219 0.1093
-0.2356 0.6838 -0.4490 0.5248
-0.1562 -0.2894 0.5437 0.7722
L =
0.0334 0 0 0
0 2.2974 0 0
0 0 2.5477 0
0 0 0 5.1215
>> Q * L.^5 * Q'
ans =
425 -162 -639 -912
-162 110 204 273
-639 204 1022 1389
-912 273 1389 2138
>> S^5
ans =
425 -162 -639 -912
-162 110 204 273
-639 204 1022 1389
-912 273 1389 2138