Matrix Factorizations and Eigenvalues

Section 4.7 Matrix Factorizations and Eigenvalues

This section is a rather rapid tour of some cool ideas that get a lot of use in applied linear algebra. We are rather light on details here. The interested reader can consult sections 8.3–8.6 in the Nicholson textbook.

🔗

Subsection 4.7.1 Matrix Factorizations

Subsubsection 4.7.1.1 Positive Operators

Let

T

be a linear operator defined by a matrix

A .

A

is symmetric (for the case of

R^{n}

) or hermitian (for the case of

C^{n}

), we say that the operator

T

is self-adjoint.

🔗

Definition 4.7.1.

A self-adjoint operator

T

is positive if

x^{H} T x \geq 0

for all vectors

x \neq 0 .

It is positive-definite if

x^{H} T x > 0

for all nonzero

x .

T = T_{A}

for some matrix

A,

we also refer to

A

as a positive(-definite) matrix.

🔗

Aside

The definition of a positive matrix is equivalent to requiring that all its eigenvalues are non-negative. Every positive matrix

A

has a unique positive square root: a matrix

R

such that

R^{2} = A .

Since

A

is symmetric/hermitian, it can be diagonalized. Writing

A = P D P^{- 1}

where

P

is orthogonal/unitary and

D = [\begin{matrix} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n} \end{matrix}],

we have

R = P E P^{- 1},

where

D = [\begin{matrix} \sqrt{λ_{1}} & 0 & \dots & 0 \\ 0 & \sqrt{λ_{2}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & \sqrt{λ_{n}} \end{matrix}] .

🔗

The following theorem gives us a simple way of generating positive matrices.

🔗

Theorem 4.7.2.

For any

n \times n

matrix

U,

the matrix

A = U^{T} U

is positive. Moreover, if

U

is invertible, then

A

is positive-definite.

🔗

Proof.

For any

x \neq 0

R^{n},

x^{T} A x = x^{T} U^{T} U x = (U x)^{T} (U x) = ‖ U x ‖^{2} \geq 0 .

🔗

What is interesting is that the converse to the above statement is also true. The Cholesky factorization of a positive-definite matrix

A

is given by

A = U^{T} U,

where

U

is upper-triangular, with positive diagonal entries.

🔗

Even better is that there is a very simple algorithm for obtaining the factorization: Carry the matrix

A

to triangular form, using only row operations of the type

R_{i} + k R_{j} \to R_{i} .

Then divide each row by the square root of the diagonal entry to obtain the matrix

U .

🔗

The SymPy library contains the cholesky() algorithm. Note however that it produces a lower triangular matrix, rather than upper triangular. (That is, the output gives

L = U^{T}

rather than

U,

so you will have

A = L L^{T} .

) Let’s give it a try. First, let’s create a positive-definite matrix.

🔗

xxxxxxxxxx
 
import sympy as sy
sy.init_printing()
B = sy.Matrix([[3,7,-4],[5,-9,2],[-3,0,6]])
A = B*B.T
A

Next, find the Cholesky factorization:

🔗

xxxxxxxxxx
 
L = A.cholesky()
L, L*L.T

xxxxxxxxxx
 
L*L.T == A

Note that

L

is not the same as the matrix

B!

🔗

Subsubsection 4.7.1.2 Singular Value Decomposition

For any

n \times n

matrix

A,

the matrices

A^{T} A

and

A A^{T}

are both positive. (Exercise!) This means that we can define

\sqrt{A^{T} A},

even if

A

itself is not symmetric or positive.

🔗

Since $A^{T} A$ is symmetric, we know that it can be diagonalized.
🔗

🔗
Since $A^{T} A$ is positive, we know its eigenvalues are non-negative.
🔗

🔗
This means we can define the singular values $σ_{i} = \sqrt{λ_{i}}$ for each $i = 1, \dots, n .$
🔗

🔗
Note: it’s possible to do this even if $A$ is not a square matrix!
🔗

🔗

🔗

The SymPy library has a function for computing the singular values of a matrix. Given a matrix A, the command A.singular_values() will return its singular values. Try this for a few different matrices below:

🔗

xxxxxxxxxx
 
A = sy.Matrix([[1,2,3],[4,5,6]])
A.singular_values()

In fact, SymPy can even return singular values for a matrix with variable entries! Try the following example from the SymPy documentation.

🔗

xxxxxxxxxx
 
x = sy.Symbol('x', real=True)
M = sy.Matrix([[0,1,0],[0,x,0],[-1,0,0]])
M,M.singular_values()

For an

n \times n

matrix

A,

we might not be able to diagonalize

A

(with a single orthonormal basis). However, it turns out that it’s always possible to find a pair of orthonormal bases

{e_{1}, \dots, e_{n}}, {f_{1}, \dots, f_{n}}

such that

A x = σ_{1} (x \cdot e_{1}) f_{1} + \dots + σ_{n} (x \cdot e_{n}) f_{n} .

In matrix form,

A = P Σ_{A} Q^{T}

for orthogonal matrices

P, Q .

🔗

In fact, this can be done even if

A

is not square, which is arguably the more interesting case! Let

A

be an

m \times n

matrix. We will find an

m \times m

orthogonal matrix

P

and

n \times n

orthogonal matrix

Q,

such that

A = P Σ_{A} Q^{T},

where

Σ_{A}

is also

m \times n .

🔗

Aside

The basis

{f_{1}, \dots, f_{n}}

is an orthonormal basis for

A^{T} A,

and the matrix

Q

is the matrix whose columns are the vectors

f_{i} .

As a result,

Q

is orthogonal.

🔗

The matrix

Σ_{A}

is the same size as

A .

First, we list the positive singular values of

A

in decreasing order:

σ_{1} \geq σ_{2} \geq \dots \geq σ_{k} > 0 .

Then, we let

D_{A} = diag (σ_{1}, \dots, σ_{k}),

and set

Σ_{A} = [\begin{matrix} D_{A} & 0 \\ 0 & 0 \end{matrix}] .

That is, we put

D_{A}

in the upper-left, and then fill in zeros as needed, until

Σ_{A}

is the same size as

A .

🔗

Next, we compute the vectors

e_{i} = \frac{1}{‖ A f_{i} ‖} A f_{i},

for

i = 1, \dots, k .

As shown in Nicolson,

{e_{1}, \dots, e_{r}}

will be an orthonormal basis for the column space of

A .

The matrix

P

is constructed by extending this to an orthonormal basis of

R^{m} .

🔗

All of this is a lot of work to do by hand, but it turns out that it can be done numerically, and more importantly, efficiently, by a computer. The SymPy library has an SVD algorithm, but it will not be efficient for larger matrices. In practice, most Python users will use the SVD algorithm provided by NumPy; we will stick with SymPy for simplicity and consistency.

🔗

Remark 4.7.3.

The version of the SVD given above is not used in computations, since it tends to be more resource intensive. In particular, it requires us to store more information than necessary: the last

n - r

rows of

Q,

and the last

m - r

columns of

P,

get multiplied by columns/rows of zeros in

Σ_{A},

so we don’t really need to keep track of these columns.

🔗

Instead, most algorithms that you find will give the

r \times r

diagonal matrix

D_{A},

consisting of the nonzero singular values, and

P

will be replaced by the

m \times r

matrix consisting of its first

r

columns, while

Q

gets replaced by the

r \times n

matrix consisting of its first

r

rows. The resulting product is still equal to the original matrix.

🔗

In some cases, even the matrix

D_{A}

is too large, and a decision is made to truncate to some smaller subset of singular values. In this case, the resulting product is no longer equal to the original matrix, but it does provide an approximation. A discussion can be found on Wikipedia.

🔗

Example 4.7.4.

Find the singular value decomposition of the matrix

A = [\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & - 1 \end{matrix}] .

🔗

Solution.

Using SymPy, we get the condensed SVD. First, let’s check the singular values.

🔗

xxxxxxxxxx
 
A = sy.Matrix([[1,1,1],[1,0,-1]])
A.singular_values()

Note that the values are not listed in decreasing order. Now, let’s ask for the singular value decomposition. The output consists of three matrices; the first line below assigns those matrices to the names P,S,Q.

🔗

xxxxxxxxxx
 
P,S,Q=A.singular_value_decomposition()
P,S,Q

Note that the output is the “condensed” version, which doesn’t match the exposition above. It also doesn’t follow the same ordering convention: we’ll need to swap columns in each of the matrices. But it does give us a decomposition of the matrix

A :

🔗

xxxxxxxxxx
 
P*S*Q.T

To match our earlier presentation, we first set

Σ_{A} = [\begin{matrix} \sqrt{3} & 0 & 0 \\ 0 & \sqrt{2} & 0 \end{matrix}] .

Next, we need to extend the

3 \times 2

matrix in the output above to a

3 \times 3

matrix. We can do this by choosing any vector orthogonal to the two existing columns, and normalizing. Let’s use entries

1 / \sqrt{6}, - 2 / \sqrt{6}, 1 / \sqrt{6} .

Noting that we also need to swap the first two columns (to match the fact that we swapped columns in

Σ_{A}

), we get the matrix

Q = [\begin{matrix} \frac{\sqrt{3}}{3} & \frac{\sqrt{2}}{2} & \frac{\sqrt{6}}{6} \\ \frac{\sqrt{3}}{3} & 0 & - \frac{\sqrt{6}}{3} \\ \frac{\sqrt{3}}{3} & - \frac{\sqrt{2}}{2} & \frac{\sqrt{6}}{6} \end{matrix}] .

Let’s check that it is indeed orthogonal.

🔗

xxxxxxxxxx
 
Q = sy.Matrix([
    [sy.sqrt(3)/3,sy.sqrt(2)/2,sy.sqrt(6)/6],
    [sy.sqrt(3)/3,0,-sy.sqrt(6)/3],
    [sy.sqrt(3)/3,-sy.sqrt(2)/2,sy.sqrt(6)/6]])
Q*Q.T

Finally, we take

P = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]

(again swapping columns), which is just the identity matrix. We therefore should expect that

P Σ_{A} Q^{T} = Σ_{A} Q^{T} = A .

Let’s check.

🔗

xxxxxxxxxx
 
S = sy.Matrix([[sy.sqrt(3),0,0],[0,sy.sqrt(2),0]])
S*Q.T

It worked!

🔗

The Singular Value Decomposition has a lot of useful appplications, some of which are described in Nicholson’s book. On a very fundamental level the SVD provides us with information on some of the most essential properties of the matrix

A,

and any system of equations with

A

as its coefficient matrix.

🔗

Recall the following definitions for an

m \times n

matrix

A :

The rank of $A$ is the number of leadning ones in the RREF of $A,$ which is also equal to the dimension of the column space of $A$ (or if you prefer, the dimension of $im (T_{A})$ ).
🔗

🔗
The column space of $A,$ denoted $col (A),$ is the subspace of $R^{m}$ spanned by the columns of $A .$ (This is the image of the matrix transformation $T_{A};$ it is also the space of all vectors $b$ for which the system $A x = b$ is consistent.)
🔗

🔗
The row space of $A,$ denoted $row (A),$ is the span of the rows of $A,$ viewed as column vectors in $R^{n} .$
🔗

🔗
The null space of $A$ is the space of solutions to the homogeneous system $A x = 0 .$ This is, of course, equal the kernel of the associated transformation $T_{A} .$
🔗

🔗

🔗

There are some interesting relationships among these spaces, which are left as an exercise.

🔗

Exercise 4.7.5.

Let

A

be an

m \times n

matrix. Prove the following statements.

🔗

(a)

(row (A))^{⊥} = null (A)

🔗

Hint.

Note that

v \in null (A)

if and only if

A v = 0,

and

v \in (row (A))^{⊥}

if and only if

v \cdot r_{i} = 0

for each row

r_{i}

A .

🔗

Note also that

(A v)^{T} = v^{T} A^{T}

is the (dot) product of

v^{T}

with each column of

A^{T},

and each column of

A^{T}

is a row of

A .

🔗

(b)

(col (A))^{⊥} = null (A^{T})

🔗

Hint.

Notice that

v \in null (A^{T})

if and only if

A^{T} v = 0,

and that

(A^{T} v)^{T} = v^{T} A .

Your reasoning should be similar to that of the previous part.

🔗

Here’s the cool thing about the SVD. Let

σ_{1} \geq σ_{2} \geq \dots \geq σ_{r} > 0

be the positive singular values of

A .

Let

q_{1}, \dots, q_{r}, \dots, q_{n}

be the orthonormal basis of eigenvectors for

A^{T} A,

and let

p_{1}, \dots, p_{r}, \dots, p_{m}

be the orthonormal basis of

R^{m}

constructed in the SVD algorithm. Then:

🔗

$rank (A) = r$
🔗

🔗
$q_{1}, \dots, q_{r}$ form a basis for $row (A) .$
🔗

🔗
$p_{1}, \dots, p_{r}$ form a basis for $col (A)$ (and thus, the “row rank” and “column rank” of $A$ are the same).
🔗

🔗
$q_{r + 1}, \dots, q_{n}$ form a basis for $null (A) .$ (And these are therefore the basis solutions of $A x = 0!$ )
🔗

🔗
$p_{r + 1}, \dots, p_{m}$ form a basis for $null (A^{T}) .$
🔗

🔗

🔗

If you want to explore this further, have a look at the excellent notebook by Dr. Juan H Klopper. The ipynb file can be found on his GitHub page. In it, he takes you through various approaches to finding the singular value decomposition, using the method above, as well as using NumPy and SciPy (which, for industrial applications, are superior to SymPy).

🔗

Subsubsection 4.7.1.3 QR Factorization

Suppose

A

is an

m \times n

matrix with independent columns. (Question: for this to happen, which is true —

m \geq n,

n \geq m ?

)

🔗

Q R

-factorization of

A

is a factorization of the form

A = Q R,

where

Q

m \times n,

with orthonormal columns, and

R

is an invertible upper-triangular (

n \times n

) matrix with positive diagonal entries. If

A

is a square matrix,

Q

will be orthogonal.

🔗

A lot of the methods we’re looking at here involve more sophisticated numerical techniques than SymPy is designed to handle. If we wanted to spend time on these topics, we’d have to learn a bit about the NumPy package, which has built in tools for finding things like polar decomposition and singular value decomposition. However, SymPy does know how to do

Q R

factorization. After defining a matrix A, we can use the command

          Q, R = A.QRdecomposition()

🔗

xxxxxxxxxx
 
A = sy.Matrix(3,3,[1,-2,3,3,-1,2,4,2,5])
Q, R = A.QRdecomposition()
A, Q, R

Let’s check that the matrix

Q

really is orthogonal:

🔗

xxxxxxxxxx
 
Q**(-1) == Q.T

Details of how to perform the QR factorization can be found in Nicholson’s textbook. It’s essentially a consequence of performing the Gram-Schmidt algorithm on the columns of

A,

and keeping track of our work.

🔗

The calculation above is a symbolic computation, which is nice for understanding what’s going on. The reason why the

Q R

factorization is useful in practice is that there are efficient numerical methods for doing it (with good control over rounding errors). Our next topic looks at a useful application of the

Q R

factorization.

🔗

Subsection 4.7.2 Computing Eigenvalues

Our first method focuses on the dominant eigenvalue of a matrix. An eigenvalue is dominant if it is larger in absolute value than all other eigenvalues. For example, if

A

has eigenvalues

1, 3, - 2, - 5,

then

- 5

is the dominant eigenvalue.

🔗

A

has eigenvalues

1, 3, 0, - 4, 4

then there is no dominant eigenvalue. Any eigenvector corresponding to a dominant eigenvalue is called a dominant eigenvector.

🔗

Subsubsection 4.7.2.1 The Power Method

If a matrix

A

has a dominant eigenvalue, there is a method for finding it (approximately) that does not involve finding and factoring the characteristic polynomial of

A .

🔗

We start with some initial guess

x_{0}

for a dominant eigenvector. We then set

x_{k + 1} = A x_{k}

for each

k \geq 0,

giving a sequence

x_{0}, A x_{0}, A^{2} x_{0}, A^{3} x_{0}, \dots .

We expect (for reasons we’ll explain) that

‖ x_{k} - x ‖ \to 0

k \to \infty,

where

x

is a dominant eigenvector. Let’s try an example.

🔗

xxxxxxxxxx
 
A = sy.Matrix(2,2,[1,-4,-3,5])
A,A.eigenvects()

The dominant eigenvalue is

λ = 7 .

Let’s try an initial guess of

x_{0} = [\begin{matrix} 1 \\ 0 \end{matrix}]

and see what happens.

🔗

xxxxxxxxxx
 
x0 = sy.Matrix(2,1,[1,0])
L = list()
for k in range(10):
    L.append(A**k*x0)
L

We might want to confirm whether that rather large fraction is close to

\frac{2}{3} .

To do so, we can get the computer to divide the numerator by the denominator.

🔗

xxxxxxxxxx
 
L[9][0]/L[9][1]

The above might show you the fraction rather than its decimal approximation. (This may depend on whether you’re on Sage or Jupyter.) To get the decimal, try wrapping the above in float() (or N, or append with .evalf()).

🔗

For the eigenvalue, we note that if

A x = λ x,

then

\frac{x \cdot A x}{‖ x ‖^{2}} = \frac{x \cdot (λ x)}{‖ x ‖^{2}} = λ .

This leads us to consider the Rayleigh quotients

r_{k} = \frac{x_{k} \cdot x_{k + 1}}{‖ x_{k} ‖^{2}} .

🔗

xxxxxxxxxx
 
M = list()
for k in range(9):
    M.append((L[k].dot(L[k+1]))/(L[k].dot(L[k])))
M

We can convert a rational number r to a float using either N(r) or r.evalf(). (The latter seems to be the better bet when working with a list.)

🔗

xxxxxxxxxx
 
M2 = list()
for k in range(9):
    M2.append((M[k]).evalf())
M2

So why does this work? Suppose

A

is diagonalizable, so that there is a basis of eigenvectors

B = {v_{1}, \dots, v_{n}}

for

R^{n} .

Suppose also that

A

has dominant eigenvalue

λ_{1},

with corresponding eigenvector

v_{1} .

Then our initial guess

x_{0}

can be written in terms of this basis:

x_{0} = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{n} v_{n},

for scalars

c_{1}, c_{2}, \dots, c_{n} .

🔗

For each natural number

k

we have

\begin{aligned} A^{k} x_{0} & = c_{1} A^{k} v_{1} + c_{2} A^{k} v_{2} + \dots + c_{n} A^{k} v_{n} \\ x_{k} & = c_{1} λ_{1}^{k} v_{1} + c_{2} λ_{2}^{k} v_{2} + \dots + c_{n} λ_{n}^{k} v_{n} . \end{aligned}

Dividing by

λ_{1}^{k}

we get

\frac{1}{λ_{1}^{k}} x_{k} = c_{1} v_{1} + c_{2} {(\frac{λ_{2}}{λ_{1}})}^{k} v_{2} + \dots + c_{n} {(\frac{λ_{n}}{λ_{1}})}^{k},

and since

λ_{1}

is larger than all the other eigenvalues in absolute value, the powers

{(\frac{λ_{m}}{λ_{1}})}^{k}

will be very small when

k

is large.

🔗

v_{1}

is an eigenvector corresponding to the dominant eigenvalue

λ_{1},

then so is the scalar multiple

c_{1} λ_{1}^{k} v_{1},

x_{k}

is approximately equal to an eigenvector.

🔗

Two things are worth noting:

The result does not depend on the initial guess $x_{0},$ unless we choose an $x_{0}$ for which the coefficient $c_{1}$ is 0. If this turns out to be the case, we must choose another initial guess.
🔗

🔗
If $A$ is not diagonalizable, we can still use this method, but we must choose $x_{0}$ from the subspace spanned by a set of eigenvectors for $A .$
🔗

🔗

🔗

Subsubsection 4.7.2.2 The QR Algorithm

Given an

n \times n

matrix

A,

we know we can write

A = Q R,

with

Q

orthogonal and

R

upper-triangular. The

Q R

-algorithm exploits this fact. We set

A_{1} = A,

and write

A_{1} = Q_{1} R_{1} .

🔗

Then we set

A_{2} = R_{1} Q_{1},

and factor:

A_{2} = Q_{2} R_{2} .

Notice

A_{2} = R_{1} Q_{1} = Q_{1}^{T} A_{1} Q_{1} .

Since

A_{2}

is similar to

A_{1},

A_{2}

has the same eigenvalues as

A_{1} = A .

🔗

Next, set

A_{3} = R_{2} Q_{2},

and factor as

A_{3} = Q_{3} R_{3} .

Since

A_{3} = Q_{2}^{T} A_{2} Q_{2},

A_{3}

has the same eigenvalues as

A_{2} .

In fact,

A_{3} = Q_{2}^{T} (Q_{1}^{T} A Q_{1}) Q_{2} = (Q_{1} Q_{2})^{T} A (Q_{1} Q_{2}) .

🔗

After

k

steps we have

A_{k + 1} = (Q_{1} \dots Q_{k})^{T} A (Q_{1} \dots Q_{k}),

which still has the same eigenvalues as

A .

By some sort of dark magic, this sequence of matrices converges to an upper triangular matrix with eigenvalues on the diagonal!

🔗

Consider the matrix

A = [\begin{matrix} 5 & - 2 & 3 \\ 0 & 4 & 0 \\ 0 & - 1 & 3 \end{matrix}]

🔗

xxxxxxxxxx
 
A = sy.Matrix(3,3,[5,-2,3,0,4,0,0,-1,3])
A.eigenvals()

xxxxxxxxxx
 
Q1,R1 = A.QRdecomposition()
A2=R1*Q1
A2,Q1,R1

Now we repeat the process:

🔗

xxxxxxxxxx
 
Q2,R2 = A2.QRdecomposition()
A3=R2*Q2
A3.evalf()

Do this a few more times, and see what results! (If someone can come up with a way to code this as a loop, let me know!) The diagonal entries should get closer to

5, 4, 3,

respectively, and the

(3, 2)

entry should get closer to

0 .

🔗

xxxxxxxxxx
 
​

xxxxxxxxxx
 
​

🔗

Exercises 4.7.3 Exercises

1.

Find the singular values

σ_{1} \geq σ_{2}

A = [\begin{array}{cc} 9 & 0 \\ 0 & - 4 \end{array}] .

🔗

2.

Find the singular values

σ_{1} \geq σ_{2} \geq σ_{3}

A = [\begin{array}{ccc} - 8 & 0 & - 2 \\ 2 & 0 & - 8 \end{array}] .

🔗

3.

Find the

Q R

factorization of the matrix

[\begin{array}{cc} - 3 & - 11 \\ - 2 & - 12 \\ - 6 & - 15 \end{array}] .

🔗

4.

Find the

Q R

factorization of the matrix

[\begin{array}{ccc} - 3 & 1 & 7 \\ - 6 & - 4 & 2 \\ - 6 & - 1 & - 1 \end{array}] .

🔗

You have attempted 1 of 7 activities on this page.

🔗

Prev Top Next