14 In-Class Assignment: Diagonalization
Contents
14 In-Class Assignment: Diagonalization#
Image from: https://en.wikipedia.org/wiki/Diagonalizable_matrix
%matplotlib inline
import matplotlib.pylab as plt
import numpy as np
import sympy as sym
sym.init_printing()
1. Pre-class Assignment Review#
15–Diagonalization_pre-class-assignment.ipynb
2. Diagonalization#
Reminder: The eigenvalues of triangular (upper and lower) and diagonal matrices are easy:
The eigenvalues for triangular matrices are the diagonal elements.
The eigenvalues for the diagonal matrices are the diagonal elements.
Diagonalization#
Definition: A square matrix \(A\) is said to be diagonalizable if there exist a matrix \(C\) such that \(D=C^{-1}AC\) is a diagonal matrix.
Definition: \(B\) is a similar matrix of \(A\) if we can find \(C\) such that \(B=C^{-1}AC\).
Given an \(n\times n\) matrix \(A\), can we find another \(n \times n\) invertable matrix \(C\) such that when \(D=C^{-1}AC\) is diagonal, i.e., \(A\) is diagonalizable?
Because \(C\) is inveritble, we have $\(C^{-1}AC=D \\ CC^{-1}AC = CD\\ AC = CD \)$
Generate \(C\) as the columns of \(n\) linearly independent vectors \((x_1...x_n)\). We can compute \(AC=CD\) as follows: $\( A\begin{bmatrix} \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ { x }_{ 1 } & { x }_{ 2 } & \dots & { x }_{ n } \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}=AC=CD=\begin{bmatrix} \vdots & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ { x }_{ 1 } & { x }_{ 2 } & \dots & { x }_{ n } \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}\begin{bmatrix} { \lambda }_{ 1 } & 0 & 0 & 0 \\ 0 & { \lambda }_{ 2 } & 0 & 0 \\ \vdots & \vdots & { \dots } & \vdots \\ 0 & 0 & 0 & { \lambda }_{ n } \end{bmatrix}\)$
Then we check the corresponding columns of the both sides. We have $\(Ax_1 = \lambda_1x_1\\\vdots\\Ax_n=\lambda x_n\)$
\(A\) has \(n\) linear independent eigenvectors.
\(A\) is said to be similar to the diagonal matrix \(D\), and the transformation of \(A\) into \(D\) is called a similarity transformation.
A simple example#
Consider the following: $\( A = \begin{bmatrix}7& -10\\3& -4\end{bmatrix},\quad C = \begin{bmatrix}2& 5\\1& 3\end{bmatrix}\)$
✅ Do this: Find the similar matrix \(D = C^{-1}AC\) of \(A\).
#Put your answer to the above question here.
from answercheck import checkanswer
checkanswer.matrix(D, '8313fe0f529090d6a8cdb36248cfdd6c');
✅ Do this: Find the eigenvalues and eigenvectors of \(A\). Set variables e1 and vec1 to be the smallest eigenvalue and its associated eigenvector and e2, vec2 to represent the largest.
#Put your answer to the above question here.
from answercheck import checkanswer
checkanswer.float(e1, "e4c2e8edac362acab7123654b9e73432");
from answercheck import checkanswer
checkanswer.float(e2, "d1bd83a33f1a841ab7fda32449746cc4");
from answercheck import checkanswer
checkanswer.eq_vector(vec1, "d28f0a721eedb3d5a4c714744883932e", decimal_accuracy = 4)
from answercheck import checkanswer
checkanswer.eq_vector(vec2, "09d9df5806bc8ef975074779da1f1023", decimal_accuracy = 4)
Theorem: Similar matrices have the same eigenvalues.
Proof: Assume \(B=C^{-1}AC\) is a similar matrix of \(A\), and \(\lambda\) is an eigenvalue of \(A\) with corresponding eigenvector \(x\). That is, $\(Ax=\lambda x\)\( Then we have \)\(B(C^{-1}x) = C^{-1}AC(C^{-1}x) = C^{-1}Ax = C^{-1}(\lambda x)= \lambda (C^{-1}x).\)\( That is \)C^{-1}x\( is an eigenvector of \)B\( with eigenvalue \)\lambda$.
A second example#
✅ Do this: Consider
$\( A = \begin{bmatrix}-4& -6\\3& 5\end{bmatrix}.\)\(
Find a matrix \)C\( such that \)C^{-1}AC$ is diagonal. (Hint, use the function diagonalize in sympy.)
#Put your answer to the above question here.
#Check the output type
assert(type(C)==sym.Matrix)
from answercheck import checkanswer
checkanswer.matrix(C,'ba963b7fef354b4a7ddd880ca4bac071')
The third example#
✅ Do this: Consider
$\( A = \begin{bmatrix}5& -3\\3& -1\end{bmatrix}.\)\(
Can we find a matrix \)C\( such that \)C^{-1}AC$ is diagonal? (Hint: find eigenvalues and eigenvectors using sympy)
#Put your answer to the above question here.
Dimensions of eigenspaces and diagonalization#
Definition: The set of all eigenvectors of a \(n\times n\) matrix corresponding to an eigenvalue \(\lambda\), together with the zero vector, is a subspace of \(\mathbb R^n\). This subspace is called eigenspace.
For the third example, we have that the characteristic equation \((\lambda-2)^2=0\).
Eigenvalue \(\lambda=2\) has multiplicity 2, but the eigenspace has dimension 1, since we can not find two linearly independent eigenvectors for \(\lambda =2\).
The dimension of an eigenspace of a matrix is less than or equal to the multiplicity of the corresponding eigenvalue as a root of the characteristic equation.
A matrix is diagonalizable if and only if the dimension of every eigenspace is equal to the multiplicity of the corresponding eigenvalue as a root of the characteristic equation.
The fourth example#
✅ Do this: Consider $\( A = \begin{bmatrix}2& -1\\1& 2\end{bmatrix}.\)\( Can we find a matrix \)C\( such that \)C^{-1}AC$ is diagonal?
#Put your answer to the above question here.
3. The Power of a Matrix#
For a diagonalizable matrix \(A\), we have \(C^{-1}AC=D\). Then we have $\(A = C D C^{-1}\)$
We have $\(A^2 = C D C^{-1} C D C^{-1} = C D^2 C^{-1}\)\( \)\(A^n = C D C^{-1} \dots C D C^{-1} = C D^n C^{-1}\)$
Because the columns of \(C\) are eigenvectors, so we can say that the eigenvectors for \(A\) and \(A^n\) are the same if \(A\) is diagonalizable.
If \(x\) is an eigenvector of \(A\) with the corresponding eigenvalue \(\lambda\), then \(x\) is also an eigenvector of \(A^n\) with the corresponding eigenvalue \(\lambda^n\).
# Here are some libraries you may need to use
%matplotlib inline
import numpy as np
import sympy as sym
import networkx as nx
import matplotlib.pyplot as plt
sym.init_printing(use_unicode=True)
✅ Do this: Consider the matrix $\( A = \begin{bmatrix}-4& -6\\3& 5\end{bmatrix}\)\( from the Second example. Calculate \)A^{-3}\( and \)A^{10}$ in two different ways:
Directly, using
A**nin Python for the appropriate values of n.
#Put your answer to the above question here.
By using the matrices \(C\) and \(D\) (you found them in the worksheet above), which diagonalize \(A\).
#Put your answer to the above question here.
Compare the two approaches. Discuss which approach you’d rather take if you were doing things by hand and why.
##Put your answer here
3. Graphs and Adjacency Matrices#
A graph is a set of vertices along with edges connecting some of the vertices. Two vertices are said to be adjacent if there is an edge between them.
For example, consider the following graph with \(n = 3\) vertices:
Vertex 1 is adjacent to vertex 2. Vertex 2 is adjacent to vertex 3. However, vertex 1 is not adjacent to vertex 3.
A walk on a graph consists of repeatedly moving from one vertex to an adjacent vertex. The length of a walk is the number of steps taken. So, the following are walks on the above graph:
\(1 \rightarrow 2 \rightarrow 1\) (length \(2\))
\(3 \rightarrow 2 \rightarrow 3 \rightarrow 2\) (length \(3\))
\(2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1\) (length \(5\))
However, \(1 \rightarrow 3\) is not a walk on the graph since there is no edge from vertex 1 to vertex 3.
The adjacency matrix of a graph with \(n\) verices is a matrix of size \(n \times n\) which is used to represented a finite graph consisting of vertices and edges between some pairs of vertices. Specifically, an adjacency matrix \(A\) has entries \(0\) or \(1\). where \(A_{ij}=1\) if vertex \(i\) is connected to vertex \(j\). Adjacency matrices have zeros on the diagonal.
So for example, the \(3 \times 3\) adjacency matrix for the above graph is $\(A = \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix}.\)$
Powers of adjacency matrices have a very special meaning. In particular, if \(A\) is the adjacency matrix of a graph G, then the matrix \(A^n\) (i.e., the matrix product of n copies of \(A\)) has an interesting interpretation: the element \((A^n)_{ij}\) gives the number of walks of length \(n\) from vertex \(i\) to vertex \(j\).
✅ Do this: Diagonalize the above matrix \(A\):
# Put your code here
A = sym.Matrix([[0,1,0],[1,0,1],[0,1,0]])
✅ Do this: Compute \(A^7\) using the diagonalization computed above.
# Put your code here
✅ Do this: Compute \(A^7\) directly.
# Put your code here
✅ Question: What is the meaning of \((A^7)_{32}\)?
Put your answer here
✅ Question: What is the number of walks of length \(9\) from vertex \(1\) to vertex \(2\)?
# Put your code here
Put your answer here
✅ Question: What is the number of walks of length \(9\) from vertex \(1\) to vertex \(3\)? Can you come up with a simple explaination for this?
Put your answer here
Written by Dr. Dirk Colbry, Michigan State University
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
###STARTFOOTER###