DLA Triangular block form

Section B.5 Triangular block form

Subsection B.5.1 Matrix and eigenvalues

Here we will use Sage to carry out the calculations in Section 30.2.

First let's load our matrix into Sage.

xxxxxxxxxx
 
A = matrix( [
  [ 3, 4,  1, -1,  0, -4,  0 ],
  [ 0, 3, -4,  0,  4,  0,  0 ],
  [ 0, 0,  5, -1, -1,  0,  0 ],
  [ 0, 0, -2,  2,  3,  0,  0 ],
  [ 0, 0,  6, -1, -2,  0,  0 ],
  [ 0, 4, -5,  0,  5, -1,  0 ],
  [ 4, 3,  1, -1,  0, -3, -1 ]
] )
print(A)

🔗

This is a

$7 \times 7$ matrix.

🔗

Eigenvalues.

🔗

Determine the eigenvalues.

xxxxxxxxxx
 
A.eigenvalues()

🔗

So we have an eigenvalue

$\lambda_1 = -1$ of algebraic multiplicity

$m_1 = 3\text{,}$ and another eigenvalue

$\lambda_2 = 3$ of algebraic multiplicity

$m_1 = 4\text{.}$

🔗

Subsection B.5.2 Analysis of $\lambda_1$

🔗

For

$\lambda_1 = -1\text{,}$ the eigensubspaces are null spaces of powers of

$(-1) I - A\text{,}$ so let's form that matrix.

xxxxxxxxxx
 
C = -1 * identity_matrix(7) - A
print(C)

🔗

Compute a basis of the eigenspace.

xxxxxxxxxx
 
C.rref()

🔗

Only one parameter is required (for

$x_7$ ), so

$\dim E_{-1}(A) = 1$ and we can span this space with the vector

$\uvec{p}_1 = (0,0,0,0,0,0,1)\text{.}$

xxxxxxxxxx
 
p1 = vector((0,0,0,0,0,0,1))
print(p1)
print(A*p1)

🔗

Notice that

$A \uvec{p}_1 = - \uvec{p}_1\text{,}$ as expected.

🔗

Since the algebraic multiplicity of this eigenvalue is

$m_1 = 3\text{,}$ we need to continue with generalized eigenvectors until we hit dimension

$3\text{.}$

🔗

Extend to a basis for the second generalized eigensubspace.

🔗

Continue on to the generalized eigensubspace of degree

$2\text{.}$ To do this, we analyze the null space of

$C^2 = \bbrac{(-1)I - A}^2\text{.}$

xxxxxxxxxx
 
(C^2).rref()

🔗

We need two parameters (for

$x_6$ and

$x_7$ ), so

$\dim E_{-1}^2(A) = 2\text{,}$ and can be spanned by the vectors

$\begin{equation*} (1,0,0,0,0,1,0) \text{,} \qquad (0,0,0,0,0,0,1) \text{.} \end{equation*}$

🔗

That second vector is already our basis vector from

$E_{-1}^1(A)\text{,}$ so take

$\uvec{p}_2 = (1,0,0,0,0,1,0)\text{.}$

xxxxxxxxxx
 
p2 = vector((1,0,0,0,0,1,0))
print(p2)
C*p2

🔗

Notice that

$\bbrac{(-1)I - A} \uvec{p}_2$ is a multiple of

$\uvec{p}_1\text{,}$ so

$\bbrac{(-1)I - A} \uvec{p}_2$ is an eigenvector, as desired.

🔗

We still don't have dimension equal to algebraic multiplicity, so continue.

🔗

Extend to a basis for the third generalized eigensubspace.

🔗

Now we move on to analyzing the null space of

$C^3$ (where

$C = (-1)I - A$ ).

xxxxxxxxxx
 
(C^3).rref()

🔗

Now we need three parameters, so finally

$\dim E_{-1}^3(A) = m_1 = 3\text{.}$ Assigning parameters to

$x_5,x_6,x_7$ leads to basis vectors

$\begin{equation*} (1,-1,0,-1,1,0,0) \text{,} \qquad (1,0,0,0,0,1,0) \text{,} \qquad (0,0,0,0,0,0,1) \text{.} \end{equation*}$

🔗

Again, the last two are actually already our basis for

$E_{-1}^2(A)\text{,}$ so set

$\uvec{p}_3 = (1,-1,0,-1,1,0,0)\text{.}$

xxxxxxxxxx
 
p3 = vector((1,-1,0,-1,1,0,0))
print(p3)
C*p3

🔗

Notice that

$C \uvec{p}_3 = -2 \uvec{p}_1 - \uvec{p}_2\text{,}$ so that

$C \uvec{p}_3$ lies in

$E_{-1}^2(A)\text{,}$ as desired.

🔗

Subsection B.5.3 Analysis of $\lambda_2$

🔗

For

$\lambda_2 = 3\text{,}$ the eigensubspaces are null spaces of powers of

$3 I - A\text{,}$ so let's form that matrix.

xxxxxxxxxx
 
C = 3 * identity_matrix(7) - A
print(C)

🔗

Compute a basis of the eigenspace.

xxxxxxxxxx
 
C.rref()

🔗

Three parameters are required, so

$\dim E_3(A) = 3$ and we are already almost up to our target multiplicity of

$m_2 = 4\text{.}$ Assign parameters to

$x_5, x_6, x_7\text{,}$ leading to basis vectors

$\begin{align*} \uvec{q}_1 \amp = (0,0,1,1,1,0,0) \text{,} \amp \uvec{q}_2 \amp = (0,1,0,0,0,1,0) \text{,} \amp \uvec{q}_3 \amp = (1,0,0,0,0,0,1) \text{.} \end{align*}$

xxxxxxxxxx
 
q1 = vector((0,0,1,1,1,0,0))
q2 = vector((0,1,0,0,0,1,0))
q3 = vector((1,0,0,0,0,0,1))
print(q1,q2,q3)
print(A*q1,A*q2,A*q3)

🔗

Notice that

$A \uvec{q}_j = 3 \uvec{q}_3\text{,}$ as expected.

🔗

Since the algebraic multiplicity of this eigenvalue is

$m_2 = 4\text{,}$ we need to continue with generalized eigenvectors until we hit dimension

$4\text{.}$

🔗

Extend to a basis for the second generalized eigensubspace.

🔗

Continue on to the generalized eigensubspace of degree

$2\text{.}$ This should be our last step for this eigenvalue, as our dimension must increase past the eigenspace dimension (which was

$3$ ), but can't increase past the algebraic multiplicity (which is

$m_2 = 4$ ). The second generalized eigensubspace

$E_3^2(A)$ is the null space of

$C^2 = \bbrac{3 I - A}^2\text{.}$

xxxxxxxxxx
 
(C^2).rref()

🔗

Now we need four parameters, as expected. Assigning parameters to

$x_4,x_5,x_6,x_7$ leads to basis vectors

$\begin{gather*} (0,0,0,1,0,0,0) \text{,}\\ (0,0,1,0,1,0,0) \text{,}\\ (0,1,0,0,0,1,0) \text{,}\\ (1,0,0,0,0,0,1) \text{.} \end{gather*}$

🔗

The last two vectors are already in our basis for

$E_3(A)\text{.}$ The first two vectors can be combined to give our other basis vector for

$E_3(A)\text{,}$ so that indicates that either one would be independent from our current basis for

$E_3(A)\text{.}$ Let's choose the simplest one of the two.

xxxxxxxxxx
 
q4 = vector((0,0,0,1,0,0,0))
print(q4)
C*q4

🔗

Notice that

$\begin{equation*} \bbrac{3 I - A} \uvec{q}_4 = \uvec{q}_1 + \uvec{q}_3\text{,} \end{equation*}$

🔗

$\bbrac{3 I - A} \uvec{q}_4$ is an eigenvector, as desired.

🔗

Since we are now at

$\dim E_3^2(A) = m_2 = 4\text{,}$ our analysis of this eigenvalue is complete.

🔗

Subsection B.5.4 The transition matrix and the triangular block form matrix

🔗

We now have a basis for each of the generalized eigenspaces

$G_{-1}(A)$ and

$G_3(A)\text{,}$ with each of these bases built up one step at a time by extending a basis for one generalized eigensubspace

$E_{\lambda_j}^k(A)$ to a basis for the next generalized eigensubspace

$E_{\lambda_j}^{k+1}(A)\text{.}$ Now let's create our transition matrix

$P\text{.}$

xxxxxxxxxx
 
P = column_matrix([p1, p2, p3, q1, q2, q3, q4])
print(P)

🔗

And now compute the form matrix directly.

xxxxxxxxxx
 
T = P.inverse() * A * P
print(T)

🔗

It worked! Notice the that there is a

$m_1 \times m_1$ (that is,

$3 \times 3$ ) scalar-triangular block with the eigenvalue

$\lambda_1 = -1$ repeated down the diagonal, and a

$m_2 \times m_2$ (that is,

$4 \times 4$ ) scalar-triangular block with the eigenvalue

$\lambda_2 = 3$ repeated down the diagonal. We can extract these blocks using Python-ic list comprehension.

xxxxxxxxxx
 
T1 = T[0:3,0:3]
T2 = T[3:7,3:7]
print(T1)
print()
print(T2)

🔗

We can also use the idea in Subsection 26.4.2 to compute

$\inv{P} A P$ by row reduction: we augment

$P$ with the result of

$A P\text{,}$ and then reducing the

$P$ part on the left to identity simultaneously applies

$\inv{P}$ to the

$A P$ part on the right.

$\begin{equation*} \left[\begin{array}{c|c} P \amp AP \end{array}\right] \qquad \rowredarrow \qquad \left[\begin{array}{c|c} I \amp \inv{P}(AP) \end{array}\right] \end{equation*}$

xxxxxxxxxx
 
P_AP = P.augment(A*P)
print(P_AP)
print()
I_iPAP = P_AP.rref()
print(I_iPAP)

🔗

As expected, there's our triangular-block form matrix on the right. We can use Python-ic list comprehension to extract it, if we like.

xxxxxxxxxx
 
T = I_iPAP[:,7:14]
print(T)

🔗

And again, we can extract the blocks.

xxxxxxxxxx
 
T1 = T[0:3,0:3]
T2 = T[3:7,3:7]
print(T1)
print()
print(T2)

Section B.5 Triangular block form

Subsection B.5.1 Matrix and eigenvalues

Eigenvalues.

Subsection B.5.2 Analysis of λ1\lambda_1

Compute a basis of the eigenspace.

Extend to a basis for the second generalized eigensubspace.

Extend to a basis for the third generalized eigensubspace.

Subsection B.5.3 Analysis of λ2\lambda_2

Compute a basis of the eigenspace.

Extend to a basis for the second generalized eigensubspace.

Subsection B.5.4 The transition matrix and the triangular block form matrix

Subsection B.5.2 Analysis of $\lambda_1$

Subsection B.5.3 Analysis of $\lambda_2$