Linear Algebra · Solutions

Eigenvalues and Eigenvectors

12 questions · about 108 minutes

Work this sheet on paper and show every step: the route is what is being tested, and the solutions are written so you can compare your method, not just your final numbers. Name every theorem you use (“by the Diagonalization Theorem”, “geometric multiplicity is at most algebraic”, “by Cayley–Hamilton”) and check its hypotheses, and use the trace and determinant to check every eigenvalue list you write down. No calculator is needed anywhere — every answer has an exact closed form. Full worked solutions are on a separate page; each question also has its own reveal, so you can check one answer without seeing the rest.

1.Computation
Let $A = (1243)$ . No characteristic polynomial is needed anywhere in this question.
1. (a)Decide, by multiplying and comparing, which of $u = (2 - 1)$ , $v = (12)$ and $w = (33)$ are eigenvectors of $A$ . For each one that is, state its eigenvalue.
2. (b)Explain why the eigenvalues found in (a) are all the eigenvalues of $A$ , and why each eigenspace is a line. Check your list against $tr A$ and $det A$ .
3. (c)Without any further row reduction, write down an eigenpair of $A^{- 1}$ , an eigenpair of $A - 2 I$ , and explain why $A^{2} + A$ is singular.
Solution
(a) Multiply and compare.
$A u = (2 - 4 4 - 3) = (- 2 1) = - 1 \cdot (2 - 1),$
so $u$ is an eigenvector with eigenvalue $- 1$ .
$A v = (1 + 8 2 + 6) = (98) .$
A multiple of $(1, 2)$ with first entry $9$ would be $(9, 18)$ , not $(9, 8)$ ; so $v$ is not an eigenvector.
$A w = (3 + 12 6 + 9) = (1515) = 5 \cdot (33),$
so $w$ is an eigenvector with eigenvalue $5$ .
(b) Count. Eigenvectors belonging to distinct eigenvalues are linearly independent, and $R^{2}$ contains at most $2$ independent vectors, so a $2 \times 2$ matrix has at most $2$ distinct eigenvalues. We have found two, $5$ and $- 1$ , so there are no others.
The same count settles the eigenspaces. A basis of $E_{5}$ together with a basis of $E_{- 1}$ is an independent set (again by the independence theorem, applied eigenvalue by eigenvalue), so $dim E_{5} + dim E_{- 1} \leq 2$ . Each dimension is at least $1$ , so each is exactly $1$ : $E_{5} = span {(1, 1)}$ and $E_{- 1} = span {(2, - 1)}$ .
Checks: $tr A = 1 + 3 = 4 = 5 + (- 1)$ ✓ and $det A = 3 - 8 = - 5 = 5 \cdot (- 1)$ ✓.
(c) Transport the eigenpairs. If $A x = λ x$ then $A^{- 1} x = \frac{1}{λ} x$ (legitimate because $0$ is not an eigenvalue, so $A$ is invertible) and $(A - 2 I) x = (λ - 2) x$ . Hence $(\frac{1}{5}, w)$ and $(- 1, u)$ are eigenpairs of $A^{- 1}$ , and $(3, w)$ and $(- 3, u)$ are eigenpairs of $A - 2 I$ .
For $A^{2} + A$ use the polynomial rule with $p (t) = t^{2} + t$ : $p (A) u = p (- 1) u = (1 - 1) u = 0$ with $u \neq = 0$ . So $A^{2} + A$ has a nontrivial null space and is singular. Equivalently, $det (A^{2} + A) = p (5) p (- 1) = 30 \cdot 0 = 0$ .
Sanity check by direct computation: $A^{2} = (981617)$ , so $A^{2} + A = (10102020)$ , whose rows are equal ✓.
2.Computation
Let
$A = 512 - 1 3 - 2 116 .$
1. (a)Show that $4$ is an eigenvalue of $A$ and find a basis for the eigenspace $E_{4}$ . State its geometric multiplicity, and verify each basis vector by multiplying it by $A$ .
2. (b)Show that $112$ is an eigenvector of $A$ and find its eigenvalue.
3. (c)Using only the trace of $A$ and the fact that a geometric multiplicity never exceeds the algebraic one, write down the complete list of eigenvalues of $A$ with multiplicity, and hence $det A$ . Is $A$ invertible?
Solution
(a) Row reduce $A - 4 I$ .
$A - 4 I = 112 - 1 - 1 - 2 112 ⟶ 100 - 1 00 100,$
subtracting row 1 from row 2 and twice row 1 from row 3. The system collapses to the single equation $x_{1} - x_{2} + x_{3} = 0$ , i.e. $x_{1} = x_{2} - x_{3}$ with $x_{2}, x_{3}$ free:
$x = x_{2} 110 + x_{3} - 1 01 .$
There are nonzero solutions, so $4$ is an eigenvalue; $E_{4} = Null (A - 4 I)$ has basis ${(1, 1, 0), (- 1, 0, 1)}$ and geometric multiplicity $2$ — the eigenspace is a plane.
Checks: $A (1, 1, 0) = (5 - 1, 1 + 3, 2 - 2) = (4, 4, 0) = 4 (1, 1, 0)$ ✓ and $A (- 1, 0, 1) = (- 5 + 1, - 1 + 1, - 2 + 6) = (- 4, 0, 4) = 4 (- 1, 0, 1)$ ✓.
(b) Multiply.
$A 112 = 5 - 1 + 2 1 + 3 + 2 2 - 2 + 12 = 6612 = 6112,$
so $(1, 1, 2)$ is an eigenvector with eigenvalue $6$ .
(c) Count with the trace. A $3 \times 3$ matrix has exactly three eigenvalues counted with algebraic multiplicity. The algebraic multiplicity of $4$ is at least its geometric multiplicity $2$ , and $6$ is a further eigenvalue, so the three slots are already full: the list is $4, 4, 6$ .
Check: $tr A = 5 + 3 + 6 = 14 = 4 + 4 + 6$ ✓. (Had the algebraic multiplicity of $4$ been $3$ , the trace would have been $12$ , so the trace alone rules that out.)
The determinant is the product of the eigenvalues, $det A = 4 \cdot 4 \cdot 6 = 96$ . Since $0$ is not an eigenvalue, $A$ is invertible.
Sanity check by cofactors along the first row: $det A = 5 (18 + 2) - (- 1) (6 - 2) + 1 (- 2 - 6) = 100 + 4 - 8 = 96$ ✓.
3.Computation
Let
$A = 201030102 .$
1. (a)Compute the characteristic polynomial $p_{A} (λ)$ by expanding along the row or column with the most zeros, factor it, and list the eigenvalues with their algebraic multiplicities. Check the list against $tr A$ and $det A$ .
2. (b)Find a basis for each eigenspace and state each geometric multiplicity.
3. (c)Expand $p_{A}$ into the form $- λ^{3} + c_{2} λ^{2} + c_{1} λ + c_{0}$ , say which two coefficients you could have predicted without expanding, and use the Cayley–Hamilton theorem to write $A^{- 1}$ as a polynomial in $A$ . Evaluate $A^{- 1}$ explicitly and check one row of $A A^{- 1} = I$ .
Solution
(a) Expand along the second row, which has two zeros:
$p_{A} (λ) = det 2 - λ 01 0 3 - λ 0 10 2 - λ = (3 - λ) det (2 - λ 1 1 2 - λ) = (3 - λ) [(2 - λ)^{2} - 1] .$
Since $(2 - λ)^{2} - 1 = (2 - λ - 1) (2 - λ + 1) = (1 - λ) (3 - λ)$ ,
$p_{A} (λ) = (1 - λ) (3 - λ)^{2} .$
Eigenvalues: $1$ with algebraic multiplicity $1$ , and $3$ with algebraic multiplicity $2$ .
Checks: $tr A = 2 + 3 + 2 = 7 = 1 + 3 + 3$ ✓. By cofactors along the first row, $det A = 2 (6 - 0) - 0 + 1 (0 - 3) = 12 - 3 = 9 = 1 \cdot 3 \cdot 3$ ✓.
(b) Row reduce each $A - λ I$ . For $λ = 3$ :
$A - 3 I = - 1 01 000 10 - 1 ⟶ - 1 00 000100,$
so $x_{1} = x_{3}$ with $x_{2}$ and $x_{3}$ free. A basis of $E_{3}$ is ${(1, 0, 1), (0, 1, 0)}$ ; geometric multiplicity $2$ .
For $λ = 1$ :
$A - I = 101020101 ⟶ 100020100,$
so $x_{2} = 0$ and $x_{1} = - x_{3}$ . A basis of $E_{1}$ is ${(1, 0, - 1)}$ ; geometric multiplicity $1$ .
Checks: $A (1, 0, 1) = (3, 0, 3)$ ✓, $A (0, 1, 0) = (0, 3, 0)$ ✓, $A (1, 0, - 1) = (2 - 1, 0, 1 - 2) = (1, 0, - 1)$ ✓. Both geometric multiplicities equal the algebraic ones, as they must for a symmetric matrix.
(c) Expand and apply Cayley–Hamilton.
$p_{A} (λ) = (1 - λ) (λ^{2} - 6 λ + 9) = - λ^{3} + 7 λ^{2} - 15 λ + 9.$
The $λ^{2}$ coefficient is $(- 1)^{n - 1} tr A = + 7$ and the constant term is $det A = 9$ ; both were predictable from the outer-coefficient formula, and both agree with (a) ✓.
Cayley–Hamilton says $p_{A} (A) = 0$ :
$- A^{3} + 7 A^{2} - 15 A + 9 I = 0 ⟹ 9 I = A^{3} - 7 A^{2} + 15 A = A (A^{2} - 7 A + 15 I) .$
Hence $A^{- 1} = \frac{1}{9} (A^{2} - 7 A + 15 I)$ . Now
$A^{2} = 504090405, A^{2} - 7 A + 15 I = 5 - 14 + 15 0 4 - 7 0 9 - 21 + 15 0 4 - 7 0 5 - 14 + 15 = 60 - 3 030 - 3 06,$
so
$A^{- 1} = \frac{1}{9} 60 - 3 030 - 3 06 = \frac{2}{3} 0 - \frac{1}{3} 0 \frac{1}{3} 0 - \frac{1}{3} 0 \frac{2}{3} .$
Check the first row of $A A^{- 1}$ : $(2, 0, 1)$ against the columns gives $\frac{4}{3} - \frac{1}{3} = 1$ , $0$ , and $- \frac{2}{3} + \frac{2}{3} = 0$ , i.e. $(1, 0, 0)$ ✓. Note also that $A^{- 1}$ has eigenvalues $1, \frac{1}{3}, \frac{1}{3}$ , whose sum $\frac{5}{3}$ equals $tr A^{- 1} = \frac{2}{3} + \frac{1}{3} + \frac{2}{3}$ ✓.
4.Proof
Throughout, $A$ is a real square matrix. Quote the characteristic-equation theorem by name where you use it.
1. (a)Prove that $A$ is singular if and only if $0$ is an eigenvalue of $A$ , by evaluating the characteristic polynomial at a single point.
2. (b)Let $A = (a c b d)$ . Prove that both eigenvalues of $A$ are real if and only if $(tr A)^{2} \geq 4 det A$ , and that they are equal if and only if equality holds.
3. (c)Deduce that if $det A < 0$ then $A$ has two distinct real eigenvalues of opposite sign and is diagonalizable. Give one $2 \times 2$ example and its eigenvalues.
Solution
(a) Evaluate $p_{A}$ at $0$ . By definition $p_{A} (λ) = det (A - λ I)$ , so $p_{A} (0) = det (A - 0 \cdot I) = det A$ .
By the characteristic-equation theorem, $0$ is an eigenvalue of $A$ if and only if $p_{A} (0) = 0$ , that is, if and only if $det A = 0$ . And $det A = 0$ is exactly the statement that $A$ is singular. $■$
(Directly from the definition: $0$ is an eigenvalue iff $A v = 0$ for some $v \neq = 0$ , iff $Null A \neq = {0}$ , iff $A$ is singular. Either route is a proof.)
(b) Write out the $2 \times 2$ characteristic polynomial.
$p_{A} (λ) = det (a - λ c b d - λ) = (a - λ) (d - λ) - b c = λ^{2} - (a + d) λ + (a d - b c) = λ^{2} - (tr A) λ + det A .$
By the characteristic-equation theorem the eigenvalues are precisely the roots of this quadratic, which the quadratic formula gives as
$λ = \frac{tr A \pm ( tr A ) ^{2} - 4 det A}{2} .$
The coefficients are real, so the roots are real if and only if the discriminant $Δ = (tr A)^{2} - 4 det A$ is non-negative, and they coincide if and only if $Δ = 0$ (the $\pm$ then contributes nothing). Both roots are real exactly when $Δ \geq 0$ , and equal exactly when $Δ = 0$ . $■$
(c) Apply (b). If $det A < 0$ then $- 4 det A > 0$ , so $Δ = (tr A)^{2} - 4 det A > 0$ regardless of the trace. By (b) the eigenvalues $λ_{1}, λ_{2}$ are real and distinct. Their product is the constant term, $λ_{1} λ_{2} = det A < 0$ , and a product of two real numbers is negative only when they have opposite signs.
Two distinct eigenvalues on a $2 \times 2$ matrix means $n$ distinct eigenvalues for $n = 2$ , so $A$ is diagonalizable by the corollary that distinct eigenvalues suffice. $■$
Example: $A = (1243)$ has $det A = - 5 < 0$ , and indeed $p_{A} (λ) = λ^{2} - 4 λ - 5 = (λ - 5) (λ + 1)$ : eigenvalues $5$ and $- 1$ , one of each sign. (Any reflection $(0110)$ , eigenvalues $\pm 1$ , is another.)
5.Computation
Let
$A = 310 - 1 10 111, B = 1 - 1 - 1 - 1 1 - 1 113 .$
1. (a)Show that $A$ and $B$ have the same characteristic polynomial, and factor it.
2. (b)For each matrix find a basis of every eigenspace, compare geometric with algebraic multiplicities, and decide whether the matrix is diagonalizable. Name the criterion you are applying.
3. (c)For the matrix that is diagonalizable, write down $P$ and $D$ with $P^{- 1} (\cdot) P = D$ and verify the factorisation column by column without inverting $P$ .
4. (d)Explain why $A$ and $B$ are not similar, even though they share a characteristic polynomial.
Solution
(a) Two characteristic polynomials. For $A$ , expand along the third row, which has two zeros:
$p_{A} (λ) = (1 - λ) det (3 - λ 1 - 1 1 - λ) = (1 - λ) [(3 - λ) (1 - λ) + 1] = (1 - λ) (λ^{2} - 4 λ + 4) = (1 - λ) (2 - λ)^{2} .$
For $B$ , expand along the first row:
$p_{B} (λ) = (1 - λ) [(1 - λ) (3 - λ) + 1] - (- 1) [- (3 - λ) + 1] + 1 [1 + (1 - λ)] .$
The last two brackets are $(λ - 2)$ and $(2 - λ)$ , which cancel, leaving $p_{B} (λ) = (1 - λ) (λ^{2} - 4 λ + 4) = (1 - λ) (2 - λ)^{2}$ , the same polynomial.
Checks: both traces are $5 = 1 + 2 + 2$ ✓; $det A = 1 \cdot (3 + 1) = 4$ and $det B = 1 (3 + 1) + 1 (- 3 + 1) + 1 (1 + 1) = 4 - 2 + 2 = 4$ , both equal to $1 \cdot 2 \cdot 2$ ✓. Each matrix has eigenvalue $1$ with algebraic multiplicity $1$ and eigenvalue $2$ with algebraic multiplicity $2$ .
(b) Eigenspaces. Matrix $A$ , $λ = 2$ :
$A - 2 I = 110 - 1 - 1 0 11 - 1 ⟶ 100 - 1 00 010,$
so $x_{3} = 0$ and $x_{1} = x_{2}$ : $E_{2} = span {(1, 1, 0)}$ , geometric multiplicity $1 < 2$ . Matrix $A$ , $λ = 1$ : $A - I = 210 - 1 00 110$ ; row 2 gives $x_{1} = - x_{3}$ , then row 1 gives $x_{2} = 2 x_{1} + x_{3} = - x_{3}$ , so $E_{1} = span {(1, 1, - 1)}$ . Check: $A (1, 1, - 1) = (3 - 1 - 1, 1 + 1 - 1, - 1) = (1, 1, - 1)$ ✓.
By the diagonalizability criterion — a matrix whose characteristic polynomial factors completely is diagonalizable iff every geometric multiplicity equals the algebraic one — $A$ is defective: it supplies only $1 + 1 = 2$ independent eigenvectors in $R^{3}$ .
Matrix $B$ , $λ = 2$ :
$B - 2 I = - 1 - 1 - 1 - 1 - 1 - 1 111 ⟶ - 1 00 - 1 00 100,$
so $x_{3} = x_{1} + x_{2}$ with $x_{1}, x_{2}$ free: $E_{2} = span {(1, 0, 1), (0, 1, 1)}$ , geometric multiplicity $2$ . Matrix $B$ , $λ = 1$ : $B - I = 0 - 1 - 1 - 1 0 - 1 112$ ; rows 1 and 2 give $x_{2} = x_{3}$ and $x_{1} = x_{3}$ , and row 3 is then $- x_{3} - x_{3} + 2 x_{3} = 0$ automatically ✓. So $E_{1} = span {(1, 1, 1)}$ , geometric multiplicity $1$ .
Both multiplicities match, so $B$ is diagonalizable.
(c) Diagonalize $B$ . Columns of $P$ are the eigenvectors, and $D$ carries the matching eigenvalues in the same order:
$P = 101011111, D = 200020001 .$
$P$ is invertible because its columns are independent ( $det P = 1 (1 - 1) - 0 + 1 (0 - 1) = - 1 \neq = 0$ ). Verify $BP = P D$ one column at a time: $B (1, 0, 1) = (1 + 1, - 1 + 1, - 1 + 3) = (2, 0, 2) = 2 (1, 0, 1)$ ✓; $B (0, 1, 1) = (- 1 + 1, 1 + 1, - 1 + 3) = (0, 2, 2) = 2 (0, 1, 1)$ ✓; $B (1, 1, 1) = (1 - 1 + 1, - 1 + 1 + 1, - 1 - 1 + 3) = (1, 1, 1) = 1 (1, 1, 1)$ ✓. Hence $P^{- 1} BP = D$ .
(d) Not similar. Suppose $B = Q^{- 1} A Q$ for some invertible $Q$ . Then $B - 2 I = Q^{- 1} (A - 2 I) Q$ , and the map $y \mapsto Q y$ is a bijection from $Null (B - 2 I)$ onto $Null (A - 2 I)$ : indeed $Q^{- 1} (A - 2 I) Q y = 0$ iff $(A - 2 I) (Q y) = 0$ . Linear bijections preserve dimension, so the geometric multiplicity of $2$ would be the same for both matrices. It is $2$ for $B$ and $1$ for $A$ , so no such $Q$ exists.
Equivalently: similarity preserves diagonalizability (if $A = QB Q^{- 1}$ and $B = P D P^{- 1}$ then $A = (QP) D (QP)^{- 1}$ ), and $B$ is diagonalizable while $A$ is not. The characteristic polynomial is a similarity invariant, but it is not a complete one.
6.Computation
Let $T (x) = A x$ with $A = (2134)$ . Write $[x]_{B}$ for the coordinate vector of $x$ relative to a basis $B$ .
1. (a)Find the eigenvalues and an eigenvector for each.
2. (b)Let $B$ consist of the two eigenvectors from (a). Compute $[T]_{B}$ directly from the definition (its $i$ th column is $[T (b_{i})]_{B}$ ), without inverting any matrix.
3. (c)Let $C = {(1, 0), (1, 1)}$ . Compute $[T]_{C}$ both from the definition and as $P^{- 1} A P$ , where $P$ has the vectors of $C$ as columns. Explain why the result is triangular, and check its trace and determinant against those of $A$ .
4. (d)Let $x = (5, 3)$ . Find $[x]_{B}$ , use $[T]_{B}$ to obtain $[T (x)]_{B}$ , convert back to standard coordinates, and confirm against $A x$ .
Solution
(a) Eigenpairs. $tr A = 6$ and $det A = 8 - 3 = 5$ , so $p_{A} (λ) = λ^{2} - 6 λ + 5 = (λ - 1) (λ - 5)$ : eigenvalues $1$ and $5$ (check: $1 + 5 = 6$ , $1 \cdot 5 = 5$ ✓).
For $λ = 1$ : $A - I = (1133)$ gives $x_{1} = - 3 x_{2}$ , so $b_{1} = (3, - 1)$ . For $λ = 5$ : $A - 5 I = (- 3 1 3 - 1)$ gives $x_{1} = x_{2}$ , so $b_{2} = (1, 1)$ .
Checks: $A (3, - 1) = (6 - 3, 3 - 4) = (3, - 1)$ ✓ and $A (1, 1) = (5, 5)$ ✓.
(b) The eigenbasis. $T (b_{1}) = b_{1} = 1 \cdot b_{1} + 0 \cdot b_{2}$ , so the first column of $[T]_{B}$ is $(1, 0)$ . $T (b_{2}) = 5 b_{2} = 0 \cdot b_{1} + 5 \cdot b_{2}$ , so the second column is $(0, 5)$ . Hence
$[T]_{B} = (1005) = D .$
No inversion was needed: the image of an eigenvector is a multiple of itself, and its coordinate vector is read off at sight.
(c) A basis that is only half an eigenbasis. From the definition: $T (1, 0) = (2, 1)$ . Solve $(2, 1) = α (1, 0) + β (1, 1)$ : the second entry gives $β = 1$ , then $α = 1$ , so the first column is $(1, 1)$ . $T (1, 1) = (5, 5) = 0 \cdot (1, 0) + 5 \cdot (1, 1)$ , so the second column is $(0, 5)$ :
$[T]_{C} = (1105) .$
As $P^{- 1} A P$ : $P = (1011)$ , $P^{- 1} = (10 - 1 1)$ , and
$A P = (2155), P^{- 1} (A P) = (2 - 1 1 5 - 5 5) = (1105) ✓ .$
It is lower triangular because the second basis vector $(1, 1)$ is an eigenvector: $T$ maps $span {(1, 1)}$ into itself, so the second column has a zero in the first slot. The first basis vector is not an eigenvector, so its column is full. The diagonal entries $1, 5$ are the eigenvalues, as they must be for a triangular matrix.
Invariants: $tr [T]_{C} = 1 + 5 = 6 = tr A$ ✓ and $det [T]_{C} = 5 = det A$ ✓, as similar matrices share both.
(d) Round trip through the eigenbasis. Solve $c_{1} (3, - 1) + c_{2} (1, 1) = (5, 3)$ : the equations are $3 c_{1} + c_{2} = 5$ and $- c_{1} + c_{2} = 3$ ; subtracting, $4 c_{1} = 2$ , so $c_{1} = \frac{1}{2}$ and $c_{2} = \frac{7}{2}$ . Thus $[x]_{B} = (\frac{1}{2}, \frac{7}{2})$ .
Apply the diagonal matrix: $[T (x)]_{B} = D (\frac{1}{2}, \frac{7}{2}) = (\frac{1}{2}, \frac{35}{2})$ .
Convert back: $T (x) = \frac{1}{2} (3, - 1) + \frac{35}{2} (1, 1) = (\frac{3 + 35}{2}, \frac{- 1 + 35}{2}) = (19, 17)$ .
Directly: $A (5, 3) = (10 + 9, 5 + 12) = (19, 17)$ ✓.
7.Computation
Let $A = (34 - 2 - 1)$ .
1. (a)Find the eigenvalues of $A$ , check them against the trace and determinant, and give their modulus and argument (the argument as an exact inverse-tangent expression).
2. (b)Find an eigenvector $v$ for the eigenvalue with negative imaginary part, and confirm that the second row of $(A - λ I) v = 0$ is satisfied automatically. Write down the real matrices $P$ and $C$ of the real canonical form $A = PC P^{- 1}$ , and verify it by checking $A P = PC$ .
3. (c)Describe geometrically what one application of $A$ does in the coordinates given by the columns of $P$ . Then determine every real $c$ for which the origin is an attractor for $x_{k + 1} = c A x_{k}$ , and say what happens at the boundary values of $c$ .
Solution
(a) Eigenvalues. $tr A = 3 - 1 = 2$ and $det A = - 3 + 8 = 5$ , so
$p_{A} (λ) = λ^{2} - 2 λ + 5, λ = \frac{2 \pm 4 - 20}{2} = 1 \pm 2 i .$
Checks: $(1 + 2 i) + (1 - 2 i) = 2$ ✓ and $(1 + 2 i) (1 - 2 i) = 1 + 4 = 5$ ✓. The modulus is $∣ λ ∣ = 1 + 4 = 5$ and the argument of $1 + 2 i$ , which lies in the first quadrant, is $φ = arctan 2$ (about $63.4°$ ).
(b) Eigenvector and real canonical form. Take $λ = 1 - 2 i$ . Then
$A - λ I = (3 - (1 - 2 i) 4 - 2 - 1 - (1 - 2 i)) = (2 + 2 i 4 - 2 - 2 + 2 i) .$
The first row says $(2 + 2 i) v_{1} = 2 v_{2}$ , i.e. $v_{2} = (1 + i) v_{1}$ . Choosing $v_{1} = 1$ gives $v = (1 1 + i)$ . Second row: $4 \cdot 1 + (- 2 + 2 i) (1 + i) = 4 + (- 2 - 2 i + 2 i + 2 i^{2}) = 4 - 4 = 0$ ✓, as it must be, since $A - λ I$ is singular.
Split into real and imaginary parts: $Re v = (1, 1)$ and $Im v = (0, 1)$ . With $λ = a - bi$ for $a = 1$ , $b = 2$ ,
$P = (1101), C = (12 - 2 1) .$
$P$ is invertible ( $det P = 1$ ). Verify $A P = PC$ :
$A P = (3 - 2 4 - 1 - 2 - 1) = (13 - 2 - 1), PC = (1 1 + 2 - 2 - 2 + 1) = (13 - 2 - 1) ✓ .$
Hence $A = PC P^{- 1}$ .
(c) Geometry and stability. In the coordinate system with axes $(1, 1)$ and $(0, 1)$ , the map $A$ acts as $C = 5 (cos φ sin φ - sin φ cos φ)$ with $cos φ = \frac{1}{5}$ , $sin φ = \frac{2}{5}$ : a counterclockwise rotation by $φ = arctan 2$ followed by a stretch by $5$ . Areas are multiplied by $det C = 5 = (5)^{2}$ ✓. Every nonzero trajectory of $A$ itself spirals outward.
The eigenvalues of $c A$ are $c (1 \pm 2 i)$ , of modulus $∣ c ∣ 5$ . The origin is an attractor exactly when every eigenvalue has modulus less than $1$ :
$∣ c ∣ 5 < 1 ⟺ - \frac{1}{5} < c < \frac{1}{5} .$
At $c = \pm \frac{1}{5}$ the modulus is exactly $1$ : trajectories neither grow nor decay but travel forever around a closed ellipse (a circle in the $P$ -coordinates), the origin being a centre. For $∣ c ∣ > \frac{1}{5}$ , which includes $c = 1$ , the origin is a repeller and trajectories spiral outward. Note that the sign of $c$ never matters: a negative $c$ adds a half-turn to each step but leaves the modulus, and hence the classification, unchanged.
8.Computation
A sequence is defined by $a_{0} = 1$ , $a_{1} = 1$ and
$a_{k + 2} = a_{k + 1} + 6 a_{k} (k \geq 0) .$
1. (a)Stack two consecutive terms as $x_{k} = (a_{k + 1} a_{k})$ and write the recurrence as $x_{k + 1} = A x_{k}$ . Find the eigenvalues and eigenvectors of $A$ , and write $A = P D P^{- 1}$ .
2. (b)Find an explicit formula for $A^{k}$ , and check it at $k = 1$ .
3. (c)Deduce a closed form for $a_{k}$ , check it against $a_{2}$ and $a_{3}$ computed from the recurrence, and determine $lim_{k \to \infty} a_{k + 1} / a_{k}$ together with the rate at which the ratio approaches its limit.
Solution
(a) The companion matrix.
$x_{k + 1} = (a_{k + 2} a_{k + 1}) = (a_{k + 1} + 6 a_{k} a_{k + 1}) = (1160) (a_{k + 1} a_{k}), A = (1160), x_{0} = (11) .$
$tr A = 1$ , $det A = - 6$ , so $p_{A} (λ) = λ^{2} - λ - 6 = (λ - 3) (λ + 2)$ : eigenvalues $3$ and $- 2$ , distinct, so $A$ is diagonalizable. For either eigenvalue, the second row of $(A - λ I) v = 0$ reads $v_{1} - λ v_{2} = 0$ , so $v = (λ, 1)$ works: $v_{1} = (3, 1)$ and $v_{2} = (- 2, 1)$ .
Checks: $A (3, 1) = (3 + 6, 3) = 3 (3, 1)$ ✓ and $A (- 2, 1) = (- 2 + 6, - 2) = - 2 (- 2, 1)$ ✓.
So $P = (31 - 2 1)$ , $D = (30 0 - 2)$ , and since $det P = 3 + 2 = 5$ ,
$P^{- 1} = \frac{1}{5} (1 - 1 23) .$
(b) Powers. $A^{k} = P D^{k} P^{- 1}$ with $D^{k} = diag (3^{k}, (- 2)^{k})$ :
$A^{k} = \frac{1}{5} (31 - 2 1) (3^{k} 0 0 (- 2)^{k}) (1 - 1 23) = \frac{1}{5} (3^{k + 1} 3^{k} - 2 (- 2)^{k} (- 2)^{k}) (1 - 1 23),$
which multiplies out to
$A^{k} = \frac{1}{5} (3^{k + 1} + 2 (- 2)^{k} 3^{k} - (- 2)^{k} 2 \cdot 3^{k + 1} - 6 (- 2)^{k} 2 \cdot 3^{k} + 3 (- 2)^{k}) .$
Check at $k = 1$ : $\frac{1}{5} (9 - 4 3 + 2 18 + 12 6 - 6) = \frac{1}{5} (55300) = (1160) = A$ ✓. Check the trace at general $k$ : $\frac{1}{5} (3^{k + 1} + 2 \cdot 3^{k} + 2 (- 2)^{k} + 3 (- 2)^{k}) = 3^{k} + (- 2)^{k}$ , the sum of the eigenvalues of $A^{k}$ ✓.
(c) Closed form. $a_{k}$ is the second entry of $x_{k} = A^{k} x_{0}$ , i.e. the second row of $A^{k}$ applied to $(1, 1)$ :
$a_{k} = \frac{1}{5} [(3^{k} - (- 2)^{k}) + (2 \cdot 3^{k} + 3 (- 2)^{k})] = \frac{3 ^{k + 1} + 2 ( - 2 ) ^{k}}{5} .$
(The same formula comes from expanding $x_{0} = \frac{3}{5} v_{1} + \frac{2}{5} v_{2}$ and reading off $x_{k} = \frac{3}{5} 3^{k} v_{1} + \frac{2}{5} (- 2)^{k} v_{2}$ .)
Checks: from the recurrence, $a_{2} = a_{1} + 6 a_{0} = 7$ and $a_{3} = a_{2} + 6 a_{1} = 13$ . From the formula, $a_{2} = \frac{27 + 8}{5} = 7$ ✓ and $a_{3} = \frac{81 - 16}{5} = 13$ ✓; also $a_{0} = \frac{3 + 2}{5} = 1$ and $a_{1} = \frac{9 - 4}{5} = 1$ ✓.
Ratio: dividing numerator and denominator by $3^{k + 1}$ ,
$\frac{a _{k + 1}}{a _{k}} = \frac{3 ^{k + 2} + 2 ( - 2 ) ^{k + 1}}{3 ^{k + 1} + 2 ( - 2 ) ^{k}} = 3 \cdot \frac{1 - \frac{4}{3} ( - \frac{2}{3} ) ^{k}}{1 + \frac{2}{3} ( - \frac{2}{3} ) ^{k}} ⟶ 3,$
because $- \frac{2}{3} < 1$ . The dominant eigenvalue $3$ is the limit, and the correction terms are of size $(\frac{2}{3})^{k}$ , so the ratio converges geometrically at the rate $∣ λ_{2} / λ_{1} ∣ = \frac{2}{3}$ per step — the power-method rate. The sign of $(- 2)^{k}$ makes the ratio alternate above and below $3$ : $a_{1} / a_{0} = 1$ , $a_{2} / a_{1} = 7$ , $a_{3} / a_{2} = \frac{13}{7}$ , $a_{4} / a_{3} = \frac{55}{13}$ .
9.Sketch
Consider the discrete dynamical system $x_{k + 1} = A x_{k}$ with
$A = \frac{1}{4} (5335) .$
A sketch without eigenvalues written beside it earns nothing here: every feature you draw must be justified.
1. (a)Find the eigenvalues and eigenvectors of $A$ and classify the origin.
2. (b)Expand $x_{0} = (1, 0)$ in the eigenbasis, write $x_{k}$ in closed form, and compute $x_{1}$ , $x_{2}$ , $x_{3}$ exactly. Do the same for $x_{0} = (0, 1)$ as far as $x_{1}$ .
3. (c)Show that the quantity $x^{2} - y^{2}$ is unchanged by one step of the system, and say what this means for the curve a trajectory travels along.
4. (d)Sketch the phase portrait on $- 5 \leq x, y \leq 5$ : draw both eigenlines with arrows showing the direction of motion along each, the two trajectories from (b) with their points marked, and at least one trajectory in each of the remaining regions. State which initial states tend to the origin.
Solution
(a) Eigenpairs and classification. $tr A = \frac{5}{2}$ and $det A = \frac{25 - 9}{16} = 1$ , so $p_{A} (λ) = λ^{2} - \frac{5}{2} λ + 1$ , and
$λ = \frac{\frac{5}{2} \pm \frac{25}{4} - 4}{2} = \frac{\frac{5}{2} \pm \frac{3}{2}}{2} \in {2, \frac{1}{2}} .$
Check: $2 + \frac{1}{2} = \frac{5}{2}$ and $2 \cdot \frac{1}{2} = 1$ ✓. For $λ = 2$ , $A - 2 I = \frac{1}{4} (- 3 3 3 - 3)$ gives $x = y$ : $v_{1} = (1, 1)$ . For $λ = \frac{1}{2}$ , $A - \frac{1}{2} I = \frac{1}{4} (3333)$ gives $x = - y$ : $v_{2} = (1, - 1)$ . Checks: $A (1, 1) = \frac{1}{4} (8, 8) = 2 (1, 1)$ ✓, $A (1, - 1) = \frac{1}{4} (2, - 2) = \frac{1}{2} (1, - 1)$ ✓.
One eigenvalue exceeds $1$ in modulus and the other is below $1$ , so the origin is a saddle point: repelling along the line $y = x$ , attracting along the line $y = - x$ .
(b) Two trajectories. Solve $c_{1} (1, 1) + c_{2} (1, - 1) = (1, 0)$ : adding and subtracting the coordinates gives $c_{1} = c_{2} = \frac{1}{2}$ . By the eigenbasis solution formula,
$x_{k} = \frac{1}{2} 2^{k} (11) + \frac{1}{2} (\frac{1}{2})^{k} (1 - 1) = (2^{k - 1} + 2^{- k - 1} 2^{k - 1} - 2^{- k - 1}) .$
So $x_{1} = (1 + \frac{1}{4}, 1 - \frac{1}{4}) = (\frac{5}{4}, \frac{3}{4})$ , $x_{2} = (2 + \frac{1}{8}, 2 - \frac{1}{8}) = (\frac{17}{8}, \frac{15}{8})$ , $x_{3} = (4 + \frac{1}{16}, 4 - \frac{1}{16}) = (\frac{65}{16}, \frac{63}{16})$ .
Check $x_{1}$ directly: $A (1, 0) = \frac{1}{4} (5, 3) = (\frac{5}{4}, \frac{3}{4})$ ✓; and $A (\frac{5}{4}, \frac{3}{4}) = \frac{1}{4} (\frac{25 + 9}{4}, \frac{15 + 15}{4}) = (\frac{34}{16}, \frac{30}{16}) = (\frac{17}{8}, \frac{15}{8})$ ✓.
For $x_{0} = (0, 1)$ : $c_{1} = \frac{1}{2}$ , $c_{2} = - \frac{1}{2}$ , so $x_{k} = (2^{k - 1} - 2^{- k - 1}, 2^{k - 1} + 2^{- k - 1})$ and $x_{1} = (\frac{3}{4}, \frac{5}{4})$ ; directly, $A (0, 1) = \frac{1}{4} (3, 5)$ ✓. This trajectory is the mirror image of the first in the line $y = x$ .
(c) An invariant. Write $x_{k + 1} = (x^{'}, y^{'})$ with $x^{'} = \frac{1}{4} (5 x + 3 y)$ and $y^{'} = \frac{1}{4} (3 x + 5 y)$ . Then $x^{'} + y^{'} = 2 (x + y)$ and $x^{'} - y^{'} = \frac{1}{2} (x - y)$ — these are just the two eigenvalues acting on the eigen-coordinates $x + y$ and $x - y$ . Multiplying,
$x^{' 2} - y^{' 2} = (x^{'} + y^{'}) (x^{'} - y^{'}) = 2 (x + y) \cdot \frac{1}{2} (x - y) = x^{2} - y^{2} .$
So every trajectory stays on one level curve $x^{2} - y^{2} = c$ . For $c \neq = 0$ these are hyperbolas whose asymptotes are the eigenlines $y = \pm x$ ; for $c = 0$ the level set is the two eigenlines themselves. (The trajectories of (b) lie on $x^{2} - y^{2} = 1$ and on $x^{2} - y^{2} = - 1$ : check $\frac{25}{16} - \frac{9}{16} = 1$ ✓.) The invariant is exactly $4 c_{1} c_{2}$ , which is preserved because one coefficient is doubled while the other is halved each step.
(d) The sketch must show the following, each for a stated reason.
The eigenline $y = x$ , drawn through the origin, with arrows pointing away from the origin in both directions: points on it are multiplied by $2$ each step.
The eigenline $y = - x$ , with arrows pointing toward the origin: points on it are halved each step. These two lines are the asymptotes of every other trajectory.
The trajectory from $(1, 0)$ : the marked points $(1, 0)$ , $(\frac{5}{4}, \frac{3}{4})$ , $(\frac{17}{8}, \frac{15}{8})$ , $(\frac{65}{16}, \frac{63}{16})$ , lying on the right branch of the hyperbola $x^{2} - y^{2} = 1$ , moving up and to the right and hugging the line $y = x$ ever more closely from below. The gaps between consecutive points roughly double each step. The trajectory from $(0, 1)$ is its mirror image on the upper branch of $x^{2} - y^{2} = - 1$ , approaching $y = x$ from above.
One trajectory in each of the other two regions: e.g. from $(- 1, 0)$ on the left branch of $x^{2} - y^{2} = 1$ , escaping along $y = x$ toward the lower left, and from $(0, - 1)$ on the lower branch of $x^{2} - y^{2} = - 1$ , also escaping toward the lower left. In every region the motion is first inward (the $(\frac{1}{2})^{k}$ term shrinks the $(1, - 1)$ -component) and then outward along $y = x$ (the $2^{k}$ term dominates).
The only initial states that tend to the origin are those with $c_{1} = 0$ , i.e. the points of the line $y = - x$ . Every other trajectory has a nonzero $2^{k}$ term and escapes to infinity with slope tending to $1$ .
10.Critique
A student is asked whether $A = (41 - 1 2)$ is diagonalizable and to compute $A^{10}$ . The submission reads:
Step 1. $tr A = 6$ and $det A = 9$ , so $p_{A} (λ) = λ^{2} - 6 λ + 9 = (λ - 3)^{2}$ . The eigenvalue $3$ is repeated.
Step 2. A repeated eigenvalue means that $A$ is not diagonalizable.
Step 3. Both eigenvalues equal $3$ , so in the eigenbasis $A$ acts as $3$ times the identity. But $3 I$ is the same matrix in every basis, so $A = 3 I$ and therefore $A^{10} = 3^{10} I$ .
Step 1 is correct, and the answer to the first question happens to be correct too.
1. (a)Find every flaw in Steps 2 and 3. For each, say precisely which theorem or definition is being misused, and give a one-line example or observation that exposes it.
2. (b)Decide correctly whether $A$ is diagonalizable, with a valid reason.
3. (c)Compute $A^{10}$ exactly. (The Cayley–Hamilton theorem is the tool; consider $N = A - 3 I$ .) Check your answer against the trace and determinant of $A^{10}$ .
Solution
(a) The flaws.
Step 2 is a non sequitur. A repeated eigenvalue does not decide anything; the diagonalizability criterion says a matrix is diagonalizable iff each geometric multiplicity equals the algebraic one, so the missing step is to compute $dim E_{3}$ . The identity matrix $I_{2}$ has the repeated eigenvalue $1$ and is diagonal already, so "repeated, therefore not diagonalizable" is false as a rule. The student's conclusion is right for this $A$ , but by luck, not by argument.
Step 3 contradicts Step 2. Speaking of "the eigenbasis" assumes a basis of eigenvectors exists, which is exactly what diagonalizable means and exactly what Step 2 just denied.
Step 3 misuses similarity. If $A$ were similar to $3 I$ then $A = P (3 I) P^{- 1} = 3 I$ , so a matrix similar to $3 I$ is $3 I$ — and $A$ is visibly not $3 I$ . What is true is that $A$ and $3 I$ share the characteristic polynomial $(λ - 3)^{2}$ ; but a shared characteristic polynomial is a necessary condition for similarity, never a sufficient one. The claim $A^{10} = 3^{10} I$ is therefore false; already $A^{2} = (156 - 6 3) \neq = 9 I$ .
(b) The correct diagnosis.
$A - 3 I = (11 - 1 - 1)$
has rank $1$ , so $E_{3} = Null (A - 3 I) = span {(1, 1)}$ has dimension $1$ , while the algebraic multiplicity of $3$ is $2$ . Geometric multiplicity is strictly less than algebraic, so by the diagonalizability criterion $A$ is defective: there is no basis of $R^{2}$ consisting of eigenvectors, since every eigenvector lies on the single line $y = x$ .
(c) Powers of a defective matrix. Let $N = A - 3 I = (11 - 1 - 1)$ . By Cayley–Hamilton, $p_{A} (A) = (A - 3 I)^{2} = 0$ , i.e. $N^{2} = 0$ ; directly, $N^{2} = (1 - 1 1 - 1 - 1 + 1 - 1 + 1) = 0$ ✓.
Since $A = 3 I + N$ and the matrices $3 I$ and $N$ commute, the binomial theorem applies, and every term containing $N^{2}$ or higher vanishes:
$A^{k} = (3 I + N)^{k} = 3^{k} I + k 3^{k - 1} N .$
Check at $k = 2$ : $9 I + 6 N = (9 + 6 6 - 6 9 - 6) = (156 - 6 3)$ , and directly $A^{2} = (16 - 1 4 + 2 - 4 - 2 - 1 + 4) = (156 - 6 3)$ ✓.
At $k = 10$ :
$A^{10} = 3^{10} I + 10 \cdot 3^{9} N = 3^{9} (3 I + 10 N) = 3^{9} (1310 - 10 - 7) .$
Checks: the eigenvalues of $A^{10}$ are $3^{10}, 3^{10}$ , so its trace should be $2 \cdot 3^{10}$ ; indeed $3^{9} (13 - 7) = 6 \cdot 3^{9} = 2 \cdot 3^{10}$ ✓. Its determinant should be $3^{20}$ ; indeed $3^{18} (13 \cdot (- 7) - (- 10) (10)) = 3^{18} (- 91 + 100) = 9 \cdot 3^{18} = 3^{20}$ ✓. The off-diagonal entries $\pm 10 \cdot 3^{9}$ are exactly what the student's $3^{10} I$ is missing: the nilpotent part grows linearly in $k$ on top of the geometric growth.
11.Proof
Let $A$ be an $n \times n$ real matrix with $A^{2} = A$ (such a matrix is called a projection). Prove the following, quoting each theorem you use by name.
1. (a)Every eigenvalue of $A$ is $0$ or $1$ .
2. (b) $E_{1} = Col A$ and $E_{0} = Null A$ , and $A$ is diagonalizable. (Do not assume in advance that both $0$ and $1$ are eigenvalues.)
3. (c) $rank A = tr A$ . Verify this on $A = \frac{1}{2} (1111)$ after checking that $A^{2} = A$ .
Solution
(a) Eigenvalues. Let $A v = λ v$ with $v \neq = 0$ . By the rule for polynomials in $A$ (eigenpairs of related matrices), $p (A) v = p (λ) v$ for every polynomial $p$ . Take $p (t) = t^{2} - t$ : then $p (A) = A^{2} - A = 0$ , so
$0 = (A^{2} - A) v = (λ^{2} - λ) v .$
Since $v \neq = 0$ , the scalar must vanish: $λ^{2} - λ = λ (λ - 1) = 0$ , so $λ \in {0, 1}$ . $■$
(b) The two eigenspaces fill the space. By definition $E_{0} = Null (A - 0 I) = Null A$ ; nothing to prove.
For $E_{1}$ , first let $x \in E_{1}$ , so $A x = x$ ; then $x = A x$ is in the column space of $A$ . Conversely let $y \in Col A$ , say $y = A z$ ; then $A y = A^{2} z = A z = y$ , so $y \in E_{1}$ . Hence $E_{1} = Col A$ . (Here $E_{1}$ and $E_{0}$ are being used for the null spaces $Null (A - I)$ and $Null A$ whether or not they are nonzero.)
By the Rank–Nullity Theorem, $dim E_{1} + dim E_{0} = rank A + nullity A = n$ .
Now assemble a basis. Let $u_{1}, \dots, u_{r}$ be a basis of $E_{1}$ ( $r = rank A$ , possibly $0$ ) and $w_{1}, \dots, w_{n - r}$ a basis of $E_{0}$ . The combined list has $n$ vectors, and it is independent: suppose
$c_{1} u_{1} + \dots + c_{r} u_{r} + d_{1} w_{1} + \dots + d_{n - r} w_{n - r} = 0 .$
Apply $A$ : each $A u_{i} = u_{i}$ and each $A w_{j} = 0$ , so $c_{1} u_{1} + \dots + c_{r} u_{r} = 0$ , forcing every $c_{i} = 0$ by independence of the $u$ 's. The original relation then reads $d_{1} w_{1} + \dots + d_{n - r} w_{n - r} = 0$ , forcing every $d_{j} = 0$ likewise.
So $A$ has $n$ linearly independent eigenvectors, and by the Diagonalization Theorem $A$ is diagonalizable: $A = P D P^{- 1}$ with $D = diag (1, \dots, 1, 0, \dots, 0)$ containing $r$ ones and $n - r$ zeros. $■$
(This is the direct argument. Alternatively, (a) shows $p_{A}$ factors completely as $\pm λ^{n - m} (λ - 1)^{m}$ , and the rank–nullity count shows the geometric multiplicities sum to $n$ , which is the diagonalizability criterion.)
(c) Rank equals trace. By (b), $A$ is similar to $D$ , and similar matrices have the same trace (the characteristic polynomial, whose $λ^{n - 1}$ coefficient carries the trace, is a similarity invariant). Hence
$tr A = tr D = r 1 + \dots + 1 + n - r 0 + \dots + 0 = r = rank A . ■$
Equivalently: the trace is the sum of the eigenvalues with algebraic multiplicity, each eigenvalue is $0$ or $1$ , and the multiplicity of $1$ is $dim E_{1} = rank A$ because $A$ is diagonalizable.
Example: $A = \frac{1}{2} (1111)$ has $A^{2} = \frac{1}{4} (2222) = A$ ✓. Its rank is $1$ (the two columns are equal) and its trace is $\frac{1}{2} + \frac{1}{2} = 1$ ✓. Geometrically it is the orthogonal projection onto the line $y = x$ : $E_{1} = span {(1, 1)}$ is the line projected onto, and $E_{0} = span {(1, - 1)}$ is the direction that is flattened.
12.Proof
Let $0 \leq a, b \leq 1$ and let
$P = (1 - a a b 1 - b),$
so that $P$ is the general $2 \times 2$ column-stochastic matrix: each step, a fraction $a$ of state 1 moves to state 2 and a fraction $b$ of state 2 moves to state 1.
1. (a)Show that the eigenvalues of $P$ are $1$ and $1 - a - b$ , with eigenvectors $(b, a)$ and $(1, - 1)$ respectively, and check the pair against the trace and determinant. Assuming $a + b > 0$ , write down the steady-state vector $q$ .
2. (b)Prove that for every probability vector $x_{0}$ ,
  
  $x_{k} = P^{k} x_{0} = q + (1 - a - b)^{k} (x_{0} - q),$
  
  and deduce exactly which values of $(a, b)$ make every chain converge to $q$ . Describe what the chain does for each of the excluded cases.
3. (c)Apply the result to $a = \frac{3}{10}$ , $b = \frac{1}{10}$ and $x_{0} = (1, 0)$ : give $q$ , the exact formula for $x_{k}$ , and the smallest $k$ for which the distance from $x_{k}$ to $q$ is less than one tenth of the distance from $x_{0}$ to $q$ .
Solution
(a) Eigenpairs by direct verification. Multiply:
$P (b a) = ((1 - a) b + ba ab + (1 - b) a) = (b a), P (1 - 1) = (1 - a - b a - 1 + b) = (1 - a - b) (1 - 1) .$
When $a + b > 0$ the vector $(b, a)$ is nonzero, so $1$ is an eigenvalue with eigenvector $(b, a)$ ; and $(1, - 1) \neq = 0$ always, so $1 - a - b$ is an eigenvalue with eigenvector $(1, - 1)$ . (If $a = b = 0$ then $P = I$ and $1 - a - b = 1$ ; the eigenvalue $1$ is repeated with $E_{1} = R^{2}$ , and the statement still holds.) A $2 \times 2$ matrix has exactly two eigenvalues with multiplicity, so this is the complete list.
Checks: $tr P = 2 - a - b = 1 + (1 - a - b)$ ✓ and $det P = (1 - a) (1 - b) - ab = 1 - a - b = 1 \cdot (1 - a - b)$ ✓.
The steady state is the eigenvector for $1$ scaled so that its entries sum to $1$ :
$q = \frac{1}{a + b} (b a) .$
(b) Convergence. Let $x_{0}$ be a probability vector. The entries of $x_{0}$ sum to $1$ and so do those of $q$ , so the entries of $x_{0} - q$ sum to $0$ : writing $x_{0} - q = (s, t)$ with $s + t = 0$ gives $x_{0} - q = s (1, - 1)$ , a multiple of the second eigenvector. Therefore, using $P^{k} q = q$ and $P^{k} (1, - 1) = (1 - a - b)^{k} (1, - 1)$ (the rule $A^{k} v = λ^{k} v$ for an eigenpair),
$x_{k} = P^{k} x_{0} = P^{k} q + P^{k} (x_{0} - q) = q + s (1 - a - b)^{k} (1, - 1) = q + (1 - a - b)^{k} (x_{0} - q) . ■$
The second term tends to $0$ for every $x_{0}$ if and only if $∣1 - a - b ∣ < 1$ , i.e. $- 1 < 1 - a - b < 1$ , i.e.
$0 < a + b < 2.$
(If $1 - a - b = \pm 1$ the term $s (1 - a - b)^{k}$ does not tend to $0$ whenever $s \neq = 0$ , i.e. whenever $x_{0} \neq = q$ .) Since $0 \leq a, b \leq 1$ , the excluded cases are exactly $a = b = 0$ and $a = b = 1$ :
$a = b = 0$ : $P = I$ , nobody ever moves, every probability vector is a steady state, and $x_{k} = x_{0}$ for all $k$ . The steady state is not unique.
$a = b = 1$ : $P = (0110)$ swaps the two states every step; $1 - a - b = - 1$ has modulus $1$ , and $x_{k}$ alternates between $x_{0}$ and $P x_{0}$ forever. The steady state $q = (\frac{1}{2}, \frac{1}{2})$ exists but is approached by nothing except itself. In both cases $P$ is not regular: no power of $I$ or of the swap matrix has all entries positive, which is what the Perron–Frobenius theorem requires.
Convergence is geometric with ratio $∣1 - a - b ∣$ , the modulus of the second eigenvalue — the smaller it is, the faster the chain forgets its starting point.
(c) A concrete chain. With $a = \frac{3}{10}$ , $b = \frac{1}{10}$ :
$P = (\frac{7}{10} \frac{3}{10} \frac{1}{10} \frac{9}{10}), q = \frac{1}{\frac{4}{10}} (\frac{1}{10} \frac{3}{10}) = (\frac{1}{4} \frac{3}{4}), 1 - a - b = \frac{3}{5} .$
Check: $P q = (\frac{7}{40} + \frac{3}{40}, \frac{3}{40} + \frac{27}{40}) = (\frac{1}{4}, \frac{3}{4}) = q$ ✓, and all entries of $P$ are positive, so $P$ is regular.
With $x_{0} = (1, 0)$ , $x_{0} - q = (\frac{3}{4}, - \frac{3}{4})$ , so
$x_{k} = (\frac{1}{4} + \frac{3}{4} (\frac{3}{5})^{k} \frac{3}{4} - \frac{3}{4} (\frac{3}{5})^{k}) .$
Check at $k = 1$ : $(\frac{1}{4} + \frac{9}{20}, \frac{3}{4} - \frac{9}{20}) = (\frac{7}{10}, \frac{3}{10})$ , which is the first column of $P$ , i.e. $P (1, 0)$ ✓.
The distance to $q$ is multiplied by exactly $\frac{3}{5}$ each step, so we need the smallest $k$ with $(\frac{3}{5})^{k} < \frac{1}{10}$ . Now $(\frac{3}{5})^{4} = \frac{81}{625} = 0.1296 > 0.1$ while $(\frac{3}{5})^{5} = \frac{243}{3125} = 0.07776 < 0.1$ , so $k = 5$ . After five steps the chain is within $\frac{243}{3125}$ of its initial gap: $x_{5} = (\frac{1}{4} + \frac{729}{12500}, \frac{3}{4} - \frac{729}{12500})$ , about $(0.308, 0.692)$ .

← Back to the question sheet