Linear Algebra · Solutions

Symmetric Matrices and Quadratic Forms

12 questions · about 107 minutes

Work this sheet on paper, showing every step — the method is what is being tested, and the solutions are written so you can check your route rather than just your answer. Name every result you use (“by the Spectral Theorem”, “by Sylvester's criterion”, “by the Rayleigh bound”) and check its hypotheses, above all that the matrix in question really is symmetric. No calculator is needed anywhere: every eigenvalue on this sheet is an integer or a simple surd, and every answer should be left exact. 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 $M = 213507 - 1 34$ and $A = 120 - 1 03$ .
1. (a)Split $M$ as $S + K$ with $S$ symmetric and $K$ skew-symmetric, and explain why this is the only such splitting.
2. (b)For $x = ⟨ 1, 1, 1 ⟩$ compute $x^{T} M x$ , $x^{T} S x$ and $x^{T} K x$ separately. Then explain — for every $x$ , not just this one — why the third number is forced to be zero.
3. (c)Compute $A^{T} A$ and $A A^{T}$ , state the size of each, and explain without multiplying anything out why the two products must have the same trace.
Solution
(a) Average with the transpose. $M^{T} = 25 - 1 103374$ , so
$S = \frac{1}{2} (M + M^{T}) = \frac{1}{2} 46260102108 = 231305154, K = \frac{1}{2} (M - M^{T}) = 0 - 2 2 202 - 2 - 2 0 .$
$S$ is its own transpose, $K$ has zero diagonal with $k_{ji} = - k_{ij}$ , and $S + K$ reproduces $M$ entry by entry.
Uniqueness: suppose $M = S^{'} + K^{'}$ with $S^{'}$ symmetric and $K^{'}$ skew. Transposing, $M^{T} = S^{'} - K^{'}$ . Adding the two equations gives $2 S^{'} = M + M^{T}$ , subtracting gives $2 K^{'} = M - M^{T}$ . So $S^{'}$ and $K^{'}$ are forced to be the matrices above.
(b) Evaluate all three. $M x = ⟨ 2 + 5 - 1, 1 + 0 + 3, 3 + 7 + 4 ⟩ = ⟨ 6, 4, 14 ⟩$ , so $x^{T} M x = 6 + 4 + 14 = 24$ .
$S x = ⟨ 6, 8, 10 ⟩$ , so $x^{T} S x = 24$ as well.
$K x = ⟨ 0 + 2 - 2, - 2 + 0 - 2, 2 + 2 + 0 ⟩ = ⟨ 0, - 4, 4 ⟩$ , so $x^{T} K x = 0 - 4 + 4 = 0$ .
The general reason: $x^{T} K x$ is a $1 \times 1$ matrix, hence equal to its own transpose,
$x^{T} K x = (x^{T} K x)^{T} = x^{T} K^{T} x = - x^{T} K x,$
so $2 x^{T} K x = 0$ . A skew-symmetric matrix contributes nothing to any quadratic form, which is why $x^{T} M x = x^{T} S x$ for every $x$ .
(c) Two Gram matrices. The columns of $A$ are $c_{1} = ⟨ 1, 2, 0 ⟩$ and $c_{2} = ⟨ - 1, 0, 3 ⟩$ , and $A^{T} A$ is the $2 \times 2$ table of their dot products:
$A^{T} A = (c_{1} \cdot c_{1} c_{2} \cdot c_{1} c_{1} \cdot c_{2} c_{2} \cdot c_{2}) = (5 - 1 - 1 10) .$
The rows of $A$ are $⟨ 1, - 1 ⟩$ , $⟨ 2, 0 ⟩$ , $⟨ 0, 3 ⟩$ , and $A A^{T}$ is the $3 \times 3$ table of their dot products:
$A A^{T} = 22 - 3 240 - 3 09 .$
Both are symmetric, as $(A^{T} A)^{T} = A^{T} A$ and $(A A^{T})^{T} = A A^{T}$ guarantee.
Trace: the diagonal of $A^{T} A$ lists the squared lengths of the columns, so $tr (A^{T} A)$ is the sum of the squares of all entries of $A$ . The diagonal of $A A^{T}$ lists the squared lengths of the rows — the same sum. Hence the traces agree without any multiplication: both equal $1 + 1 + 4 + 0 + 0 + 9 = 15$ , and indeed $5 + 10 = 15 = 2 + 4 + 9$ .
2.Proof
Let $S$ and $T$ be symmetric $n \times n$ matrices. Prove each statement directly from the definition $A^{T} = A$ and the rules for transposes; no eigenvalues are needed.
1. (a)Prove that $ST$ is symmetric if and only if $ST = TS$ , and give an explicit pair of symmetric $2 \times 2$ matrices whose product is not symmetric.
2. (b)Prove that a square matrix $M$ satisfies $x^{T} M x = 0$ for every $x \in R^{n}$ if and only if $M$ is skew-symmetric.
3. (c)Prove that a matrix which is both symmetric and orthogonal satisfies $A^{2} = I$ , and exhibit such a $2 \times 2$ matrix other than $\pm I$ . What does $A^{2} = I$ force the eigenvalues of $A$ to be?
Solution
(a) Transpose the product. By the reversal rule, $(ST)^{T} = T^{T} S^{T} = TS$ , using $S^{T} = S$ and $T^{T} = T$ . Therefore
$ST is symmetric ⟺ (ST)^{T} = ST ⟺ TS = ST .$
For the example take $S = (1221)$ and $T = (10 0 - 1)$ , both symmetric. Then
$ST = (12 - 2 - 1), TS = (1 - 2 2 - 1),$
which differ, and $ST$ is visibly not symmetric (its off-diagonal entries are $- 2$ and $2$ ). $■$
(b) Split off the symmetric part. ( $\Leftarrow$ ) If $M^{T} = - M$ , then the $1 \times 1$ matrix $x^{T} M x$ equals its own transpose:
$x^{T} M x = (x^{T} M x)^{T} = x^{T} M^{T} x = - x^{T} M x,$
so $2 x^{T} M x = 0$ for every $x$ .
( $\Rightarrow$ ) Write $M = S + K$ with $S = \frac{1}{2} (M + M^{T})$ symmetric and $K = \frac{1}{2} (M - M^{T})$ skew. By the direction just proved, $x^{T} K x = 0$ , so the hypothesis says $x^{T} S x = 0$ for every $x$ . Take $x = e_{i}$ : this gives $s_{ii} = 0$ . Take $x = e_{i} + e_{j}$ with $i \neq = j$ : expanding, $s_{ii} + s_{jj} + s_{ij} + s_{ji} = 2 s_{ij} = 0$ , so $s_{ij} = 0$ . Hence $S = 0$ and $M = K$ is skew-symmetric. $■$
(The key step is that a symmetric matrix is determined by its quadratic form — the same argument that shows the matrix of a form is unique.)
(c) Combine the two identities. Orthogonal means $A^{T} A = I$ ; symmetric means $A^{T} = A$ . Substituting the second into the first, $A^{2} = AA = A^{T} A = I$ . $■$
Example: $A = (0110)$ . It is symmetric, its columns are orthonormal, and $A^{2} = I$ while $A \neq = \pm I$ . Geometrically it is the reflection across the line $y = x$ .
Eigenvalues: if $A v = λ v$ with $v \neq = 0$ , then $v = A^{2} v = λ^{2} v$ , so $λ^{2} = 1$ and $λ = \pm 1$ . Combined with the Spectral Theorem, $A = Q Λ Q^{T}$ with every diagonal entry of $Λ$ equal to $\pm 1$ : a symmetric orthogonal matrix is exactly a reflection across the $+ 1$ eigenspace. For the example, $⟨ 1, 1 ⟩$ has eigenvalue $1$ and $⟨ 1, - 1 ⟩$ has eigenvalue $- 1$ .
3.Computation
Let $A = (22 2 - 1)$ .
1. (a)Find the eigenvalues of $A$ and check them against the trace and the determinant.
2. (b)Find an orthogonal matrix $Q$ and a diagonal matrix $Λ$ with $A = Q Λ Q^{T}$ . Name the result that guarantees you never needed to check that your two eigenvectors are perpendicular — and then check it anyway.
3. (c)Multiply out $Q Λ Q^{T}$ and confirm that it equals $A$ . Then describe in one sentence what $A$ does to the plane, in terms of the two directions you found.
Solution
(a) Characteristic polynomial. $tr A = 1$ and $det A = - 2 - 4 = - 6$ , so
$det (A - λ I) = λ^{2} - λ - 6 = (λ - 3) (λ + 2),$
giving $λ_{1} = 3$ and $λ_{2} = - 2$ . Check: $3 + (- 2) = 1 = tr A$ and $3 \cdot (- 2) = - 6 = det A$ . Both real, as the real-eigenvalue lemma for symmetric matrices promises.
(b) Eigenvectors, then normalise. For $λ = 3$ : $A - 3 I = (- 1 2 2 - 4)$ , and the first row says $- x + 2 y = 0$ , so $x = 2 y$ . Take $⟨ 2, 1 ⟩$ , of length $5$ : $q_{1} = \frac{1}{5} ⟨ 2, 1 ⟩$ .
For $λ = - 2$ : $A + 2 I = (4221)$ , and $2 x + y = 0$ , so $y = - 2 x$ . Take $⟨ 1, - 2 ⟩$ : $q_{2} = \frac{1}{5} ⟨ 1, - 2 ⟩$ .
The orthogonality lemma — eigenvectors of a symmetric matrix belonging to distinct eigenvalues are orthogonal — guarantees $q_{1} ⊥ q_{2}$ in advance, since $3 \neq = - 2$ . Checking anyway: $⟨ 2, 1 ⟩ \cdot ⟨ 1, - 2 ⟩ = 2 - 2 = 0$ . No Gram–Schmidt step is needed because each eigenspace is one-dimensional.
$Q = \frac{1}{5} (21 1 - 2), Λ = (30 0 - 2) .$
$Q^{T} Q = \frac{1}{5} (4 + 1 2 - 2 2 - 2 1 + 4) = I$ , so $Q$ is orthogonal. (Its determinant is $- 1$ ; replacing $q_{2}$ by $- q_{2}$ would make $Q$ a rotation, and either choice is correct.)
(c) Multiply back. First $Q Λ = \frac{1}{5} (63 - 2 4)$ , then with $Q^{T} = \frac{1}{5} (21 1 - 2)$ ,
$Q Λ Q^{T} = \frac{1}{5} (12 - 2 6 + 4 6 + 4 3 - 8) = \frac{1}{5} (1010 10 - 5) = (22 2 - 1) = A .$
Geometry: $A$ stretches the plane by a factor $3$ along the direction $⟨ 2, 1 ⟩$ and by a factor $2$ with a flip along the perpendicular direction $⟨ 1, - 2 ⟩$ — a pure stretch along two perpendicular axes, with no shear, which is what the Spectral Theorem says every symmetric matrix does.
4.Computation
Let $B = (8 - 2 - 2 5)$ .
1. (a)Write $B = λ_{1} P_{1} + λ_{2} P_{2}$ , where $P_{1}$ and $P_{2}$ are the matrices of the orthogonal projections onto the two eigen-directions. Verify $P_{1} + P_{2} = I$ and $P_{1} P_{2} = 0$ explicitly.
2. (b)Use the decomposition to write down the positive semidefinite square root $B^{1/2}$ , and square it to check. Then write down a second symmetric square root of $B$ and say why it does not deserve the name $B^{1/2}$ .
3. (c)Use the decomposition to write down $B^{- 1}$ , and check it against the usual formula for the inverse of a $2 \times 2$ matrix.
Solution
(a) Eigenvalues, eigenvectors, projections. $tr B = 13$ and $det B = 40 - 4 = 36$ , so $λ^{2} - 13 λ + 36 = (λ - 9) (λ - 4)$ : the eigenvalues are $9$ and $4$ .
For $λ = 9$ : $B - 9 I = (- 1 - 2 - 2 - 4)$ gives $x = - 2 y$ , so $q_{1} = \frac{1}{5} ⟨ 2, - 1 ⟩$ . For $λ = 4$ : $B - 4 I = (4 - 2 - 2 1)$ gives $y = 2 x$ , so $q_{2} = \frac{1}{5} ⟨ 1, 2 ⟩$ . They are orthogonal, as the lemma requires: $2 - 2 = 0$ .
The projections are the outer products of the unit vectors:
$P_{1} = q_{1} q_{1}^{T} = \frac{1}{5} (4 - 2 - 2 1), P_{2} = q_{2} q_{2}^{T} = \frac{1}{5} (1224) .$
Check the decomposition: $9 P_{1} + 4 P_{2} = \frac{1}{5} (36 + 4 - 18 + 8 - 18 + 8 9 + 16) = (8 - 2 - 2 5) = B$ .
Check the projection identities: $P_{1} + P_{2} = \frac{1}{5} (5005) = I$ , and
$P_{1} P_{2} = \frac{1}{25} (4 - 4 - 2 + 2 8 - 8 - 4 + 4) = 0.$
(b) Take square roots of the eigenvalues only. Since $P_{j} P_{k} = 0$ for $j \neq = k$ and $P_{k}^{2} = P_{k}$ , any $α P_{1} + β P_{2}$ squares to $α^{2} P_{1} + β^{2} P_{2}$ . The positive semidefinite root uses the nonnegative roots $9 = 3$ and $4 = 2$ :
$B^{1/2} = 3 P_{1} + 2 P_{2} = \frac{1}{5} (12 + 2 - 6 + 4 - 6 + 4 3 + 8) = \frac{1}{5} (14 - 2 - 2 11) .$
Squaring directly: $\frac{1}{25} (196 + 4 - 28 - 22 - 28 - 22 4 + 121) = \frac{1}{25} (200 - 50 - 50 125) = (8 - 2 - 2 5) = B$ .
A second symmetric square root: flip one sign, $3 P_{1} - 2 P_{2} = \frac{1}{5} (12 - 2 - 6 - 4 - 6 - 4 3 - 8) = (2 - 2 - 2 - 1)$ . Its square is $(4 + 4 - 4 + 2 - 4 + 2 4 + 1) = B$ as well. But it has the eigenvalue $- 2 < 0$ , so it is not positive semidefinite; the name $B^{1/2}$ is reserved for the unique positive semidefinite root, in the same way that $9$ means $3$ and not $- 3$ . (There are four symmetric roots altogether, $\pm 3 P_{1} \pm 2 P_{2}$ .)
(c) Reciprocals of the eigenvalues. $B^{- 1} = \frac{1}{9} P_{1} + \frac{1}{4} P_{2}$ , so
$B^{- 1} = \frac{1}{5} (\frac{4}{9} + \frac{1}{4} - \frac{2}{9} + \frac{1}{2} - \frac{2}{9} + \frac{1}{2} \frac{1}{9} + 1) = \frac{1}{5} (\frac{25}{36} \frac{5}{18} \frac{5}{18} \frac{10}{9}) = (\frac{5}{36} \frac{1}{18} \frac{1}{18} \frac{2}{9}) .$
The $2 \times 2$ formula gives $B^{- 1} = \frac{1}{d e t B} (5228) = \frac{1}{36} (5228)$ , and $\frac{2}{36} = \frac{1}{18}$ , $\frac{8}{36} = \frac{2}{9}$ . The two agree.
5.Computation
Let $Q (x, y, z) = x^{2} + 5 y^{2} + 3 z^{2} + 4 x y - 2 x z + 2 yz$ .
1. (a)Write down the symmetric matrix $A$ with $Q (x) = x^{T} A x$ , and compute $det A$ .
2. (b)Complete the square to write $Q = \pm u^{2} \pm v^{2} \pm w^{2}$ , where $u, v, w$ are linear expressions in $x, y, z$ that you must state. Read off the signature $(p, q)$ and classify the form.
3. (c)Exhibit a nonzero vector at which $Q < 0$ and one at which $Q > 0$ , computing both values in full from the original polynomial.
4. (d)The three coefficients in (b) are not the eigenvalues of $A$ . Explain why not, quote the theorem that says the signature nevertheless matches the signs of the eigenvalues, and check that this count is consistent with $det A$ and $tr A$ .
Solution
(a) Halve the cross terms. The diagonal carries the coefficients of the squares, $1, 5, 3$ ; each off-diagonal entry is half the coefficient of the corresponding cross term: $a_{12} = 2$ , $a_{13} = - 1$ , $a_{23} = 1$ . So
$A = 12 - 1 251 - 1 13 .$
Expanding along the first row, $det A = 1 \cdot (15 - 1) - 2 \cdot (6 + 1) + (- 1) \cdot (2 + 5) = 14 - 14 - 7 = - 7$ .
(b) Complete the square in $x$ , then in $y$ . Gather every term containing $x$ : $x^{2} + 4 x y - 2 x z = (x + 2 y - z)^{2} - (2 y - z)^{2} = (x + 2 y - z)^{2} - 4 y^{2} + 4 yz - z^{2}$ . Hence
$Q = (x + 2 y - z)^{2} + (5 - 4) y^{2} + (2 + 4) yz + (3 - 1) z^{2} = (x + 2 y - z)^{2} + y^{2} + 6 yz + 2 z^{2} .$
Now gather the $y$ terms: $y^{2} + 6 yz = (y + 3 z)^{2} - 9 z^{2}$ , so
$Q = (x + 2 y - z)^{2} + (y + 3 z)^{2} - 7 z^{2} = u^{2} + v^{2} - 7 w^{2}, u = x + 2 y - z, v = y + 3 z, w = z .$
(A coefficient of $- 7$ rather than $- 1$ is fine: rescaling $w$ to $7 z$ would give $- w^{'2}$ , and the signs are all that matter.) Two positive squares and one negative: the signature is $(p, q) = (2, 1)$ , and the form is indefinite.
(c) Read a vector off the squares. To make $Q$ negative kill both positive squares: $u = v = 0$ , $w = 1$ . From $w = 1$ , $z = 1$ ; from $v = 0$ , $y = - 3$ ; from $u = 0$ , $x = - 2 y + z = 7$ . So try $⟨ 7, - 3, 1 ⟩$ :
$Q (7, - 3, 1) = 49 + 45 + 3 + 4 (7) (- 3) - 2 (7) (1) + 2 (- 3) (1) = 97 - 84 - 14 - 6 = - 7,$
which is exactly $- 7 w^{2}$ , as it should be. For a positive value take $⟨ 1, 0, 0 ⟩$ : $Q = 1 > 0$ .
(d) Congruence is not similarity. The substitution $y = ⟨ u, v, w ⟩ = P x$ with $P = 100210 - 1 31$ (invertible, $det P = 1$ ) turns $Q$ into $y^{T} D y$ with $D = diag (1, 1, - 7)$ ; that is, $A = P^{T} D P$ . This is a congruence, not a similarity ( $P^{T} \neq = P^{- 1}$ ), so $A$ and $D$ need not share eigenvalues — and they do not: $tr A = 1 + 5 + 3 = 9$ , whereas $1 + 1 - 7 = - 5$ . The eigenvalues of $A$ sum to $9$ , so they are certainly not $1, 1, - 7$ .
What congruence does preserve is the inertia. By Sylvester's law of inertia, congruent matrices have the same number of positive, negative and zero eigenvalues, and $A = P^{T} D P$ is congruent to $D$ . So $A$ has exactly two positive eigenvalues and one negative.
Consistency: the product of the eigenvalues is $det A = - 7 < 0$ , which requires an odd number of negative eigenvalues — one or three. Three negatives would give a negative trace, but $tr A = 9 > 0$ . So exactly one is negative, matching $(2, 1)$ . As a final check, $det A = det (P^{T}) det D det P = 1 \cdot (- 7) \cdot 1 = - 7$ , agreeing with (a).
6.Critique
Two arguments follow. Each contains exactly one false step. For each argument, quote the false step, name the theorem or hypothesis that is being misused, and repair the argument to a correct conclusion with the correct numbers.
1. (a)“Let $A = 211121112$ . Its characteristic polynomial is $- (λ - 4) (λ - 1)^{2}$ , so the eigenvalues are $4, 1, 1$ . For $λ = 4$ an eigenvector is $v_{1} = ⟨ 1, 1, 1 ⟩$ . For $λ = 1$ , every row of $A - I$ is $(111)$ , so the eigenspace is the plane $x + y + z = 0$ , with basis $w_{1} = ⟨ 1, - 1, 0 ⟩$ , $w_{2} = ⟨ 0, 1, - 1 ⟩$ . Eigenvectors of a symmetric matrix are orthogonal, so $v_{1}, w_{1}, w_{2}$ are mutually orthogonal; normalising gives $q_{1} = v_{1} / 3$ , $q_{2} = w_{1} / 2$ , $q_{3} = w_{2} / 2$ , and with $Q = [q_{1} q_{2} q_{3}]$ we have $A = Q diag (4, 1, 1) Q^{T}$ .”
2. (b)“Let $M = (2013)$ . Its eigenvalues $2$ and $3$ are distinct, so $M$ is diagonalisable: with $P = (1011)$ and $D = diag (2, 3)$ we have $M = P D P^{- 1}$ . Therefore $M^{5} = P D^{5} P^{T} = (275243243243)$ .”
Solution
(a) The false step is “Eigenvectors of a symmetric matrix are orthogonal, so $v_{1}, w_{1}, w_{2}$ are mutually orthogonal.” Everything before it is correct: $A = I + J$ with $J$ the all-ones matrix, so the eigenvalues are $1 + 3 = 4$ and $1 + 0 = 1$ (twice), and $A - I = J$ does have null space $x + y + z = 0$ .
The lemma being misquoted says that eigenvectors belonging to distinct eigenvalues are orthogonal. It applies to $v_{1}$ against $w_{1}$ and $w_{2}$ (and indeed $1 - 1 + 0 = 0$ and $0 + 1 - 1 = 0$ ). It says nothing about $w_{1}$ and $w_{2}$ , which belong to the same eigenvalue, and in fact $w_{1} \cdot w_{2} = 0 - 1 + 0 = - 1 \neq = 0$ . So $Q$ is not orthogonal — $Q^{T} Q$ has $(2, 3)$ entry $q_{2} \cdot q_{3} = - \frac{1}{2}$ — and the claimed factorisation is false. A quick way to see the damage: the three “projections” $q_{k} q_{k}^{T}$ should sum to $I$ , but their $(1, 1)$ entries sum to $\frac{1}{3} + \frac{1}{2} + 0 = \frac{5}{6}$ .
Repair: run Gram–Schmidt inside the repeated eigenspace, which stays within the plane and so preserves the eigenvector property:
$w_{2}^{'} = w_{2} - \frac{w _{2} \cdot w _{1}}{w _{1} \cdot w _{1}} w_{1} = ⟨ 0, 1, - 1 ⟩ + \frac{1}{2} ⟨ 1, - 1, 0 ⟩ = ⟨ \frac{1}{2}, \frac{1}{2}, - 1 ⟩ ∥ ⟨ 1, 1, - 2 ⟩ .$
Check: $⟨ 1, 1, - 2 ⟩$ has coordinate sum $0$ (so it is still an eigenvector for $1$ ), and $⟨ 1, 1, - 2 ⟩ \cdot ⟨ 1, - 1, 0 ⟩ = 0$ . Normalising ( $∥ ⟨ 1, 1, - 2 ⟩ ∥ = 6$ ),
$Q = \frac{1}{3} \frac{1}{3} \frac{1}{3} \frac{1}{2} - \frac{1}{2} 0 \frac{1}{6} \frac{1}{6} - \frac{2}{6}, Λ = diag (4, 1, 1),$
and now $Q^{T} Q = I$ , so $A = Q Λ Q^{T}$ is correct.
(b) The false step is “ $M^{5} = P D^{5} P^{T}$ .” The diagonalisation itself is right: $M ⟨ 1, 0 ⟩ = 2 ⟨ 1, 0 ⟩$ and $M ⟨ 1, 1 ⟩ = ⟨ 3, 3 ⟩ = 3 ⟨ 1, 1 ⟩$ , so $M = P D P^{- 1}$ with the stated $P$ and $D$ , and $M^{5} = P D^{5} P^{- 1}$ .
The formula $A^{m} = Q Λ^{m} Q^{T}$ requires $Q$ to be orthogonal, so that $Q^{- 1} = Q^{T}$ ; that is available exactly when the matrix is symmetric, by the Spectral Theorem. $M$ is not symmetric, its eigenvectors are not orthogonal ( $⟨ 1, 0 ⟩ \cdot ⟨ 1, 1 ⟩ = 1$ ), and $P^{T} P = (1112) \neq = I$ . Replacing $P^{- 1}$ by $P^{T}$ is simply an error. Two tell-tales in the student's answer: it is symmetric, whereas every power of an upper-triangular matrix is upper-triangular; and its diagonal should be $2^{5} = 32$ and $3^{5} = 243$ , not $275$ and $243$ .
Repair: $P^{- 1} = (10 - 1 1)$ , so
$M^{5} = P D^{5} P^{- 1} = (320243243) (10 - 1 1) = (320211243) .$
Sanity check by squaring: $M^{2} = (4059)$ , $M^{4} = (1606581)$ , $M^{5} = M^{4} M = (320 16 + 195 243) = (320211243)$ .
7.Sketch
Consider the curve $8 x^{2} - 4 x y + 5 y^{2} = 36$ .
A sketch with no working beside it earns nothing here: every axis, length and point you draw must come from an eigenvalue or an eigenvector.
1. (a)Write down the matrix of the form, find its eigenvalues, and classify the curve, naming the result that licenses the classification.
2. (b)Find unit eigenvectors, write the equation in principal-axis coordinates $y_{1}, y_{2}$ , and give the exact lengths and directions of the semi-axes. Check that $tan 2 θ = \frac{2 b}{a - c}$ agrees with the direction you found.
3. (c)Find the four vertices and the four intercepts with the coordinate axes, exactly. Then sketch the curve, drawing both principal axes as dashed lines through the origin and labelling every vertex and intercept. Finally, say in one sentence why the curve leans into the first and third quadrants rather than the second and fourth.
Solution
(a) Matrix and eigenvalues. With $a = 8$ , $c = 5$ and the cross coefficient $- 4$ halved to $b = - 2$ ,
$A = (8 - 2 - 2 5), tr A = 13, det A = 40 - 4 = 36,$
so $λ^{2} - 13 λ + 36 = (λ - 9) (λ - 4)$ and the eigenvalues are $9$ and $4$ . Both positive, and the right-hand side $36$ is positive, so by the classification of central conics (a corollary of the principal axes theorem) the curve is an ellipse. The discriminant test agrees: $a c - b^{2} = det A = 36 > 0$ .
(b) Principal axes. For $λ = 9$ : $(8 - 9) x - 2 y = 0$ gives $x = - 2 y$ , so $q_{1} = \frac{1}{5} ⟨ 2, - 1 ⟩$ . For $λ = 4$ : $4 x - 2 y = 0$ gives $y = 2 x$ , so $q_{2} = \frac{1}{5} ⟨ 1, 2 ⟩$ . (Orthogonal, as the lemma requires: $2 - 2 = 0$ .)
With $x = Q y$ , $Q = [q_{1} q_{2}]$ , the principal axes theorem turns the equation into
$9 y_{1}^{2} + 4 y_{2}^{2} = 36, i.e. \frac{y _{1}^{2}}{4} + \frac{y _{2}^{2}}{9} = 1.$
The semi-axis along $q_{1}$ has length $36/9 = 2$ ; the semi-axis along $q_{2}$ has length $36/4 = 3$ . So the major axis (length $3$ ) points along $⟨ 1, 2 ⟩$ , the eigenvector of the smaller eigenvalue — a large eigenvalue means a short axis, because that direction climbs to the level $36$ fastest.
Angle check: $tan 2 θ = \frac{2 b}{a - c} = \frac{- 4}{3}$ . The direction $⟨ 2, - 1 ⟩$ has $tan θ = - \frac{1}{2}$ , and the double-angle formula gives $tan 2 θ = \frac{2 ( - \frac{1}{2} )}{1 - \frac{1}{4}} = - \frac{4}{3}$ . The formula and the eigenvector agree: the minor axis sits about $26. 6^{\circ}$ below the $x$ -axis, the major axis about $63. 4^{\circ}$ above it.
(c) Vertices, intercepts, sketch. The vertices are the ends of the semi-axes:
$\pm 2 q_{1} = \pm ⟨ \frac{4}{5}, - \frac{2}{5} ⟩ \approx \pm ⟨ 1.79, - 0.89 ⟩, \pm 3 q_{2} = \pm ⟨ \frac{3}{5}, \frac{6}{5} ⟩ \approx \pm ⟨ 1.34, 2.68 ⟩ .$
Check one of each on the original equation: at $⟨ \frac{4}{5}, - \frac{2}{5} ⟩$ , $8 \cdot \frac{16}{5} + 4 \cdot \frac{8}{5} + 5 \cdot \frac{4}{5} = \frac{128 + 32 + 20}{5} = 36$ ; at $⟨ \frac{3}{5}, \frac{6}{5} ⟩$ , $8 \cdot \frac{9}{5} - 4 \cdot \frac{18}{5} + 5 \cdot \frac{36}{5} = \frac{72 - 72 + 180}{5} = 36$ .
Intercepts: on $y = 0$ , $8 x^{2} = 36$ gives $x = \pm \frac{3}{2} = \pm \frac{3 2}{2} \approx \pm 2.12$ ; on $x = 0$ , $5 y^{2} = 36$ gives $y = \pm \frac{6}{5} \approx \pm 2.68$ .
The sketch: draw the dashed line through the origin with slope $2$ (the major axis) and the dashed line with slope $- \frac{1}{2}$ (the minor axis), perpendicular to each other. Mark the two major vertices at distance $3$ from the origin along the first line and the two minor vertices at distance $2$ along the second, and draw the ellipse through all four, tangent to the perpendicular direction at each. Mark the intercepts $(\pm 2.12, 0)$ and $(0, \pm 2.68)$ and confirm the curve passes through them. Note that the intercepts are not the extreme points of the ellipse: the curve pokes slightly beyond them, to $∣ x ∣ = 5 \approx 2.24$ and $∣ y ∣ = 22 \approx 2.83$ , before turning back. (Those extremes come from asking when the equation, read as a quadratic in one variable, has a double root.)
Why it leans into quadrants I and III: the cross term $- 4 x y$ is negative where $x$ and $y$ have the same sign, so in those quadrants the form grows more slowly and a point can travel farther from the origin before reaching the level $36$ . In eigenvalue language, the smaller eigenvalue $4$ belongs to $⟨ 1, 2 ⟩$ , which points into quadrant I, and the semi-axis there is the longer one, $36/4 = 3$ .
8.Computation
Let $Q (x, y, z) = - x^{2} - y^{2} - z^{2} - 4 x y - 4 x z - 4 yz$ , and let $A$ be its matrix.
1. (a)Write down $A$ and find its eigenvalues without expanding a $3 \times 3$ determinant, by expressing $A$ in terms of $I$ and the all-ones matrix $J$ . Check with the trace.
2. (b)Find the maximum and the minimum of $Q$ on the unit sphere $x^{2} + y^{2} + z^{2} = 1$ , and describe the complete set of points at which each is attained. Then evaluate the Rayleigh quotient at $⟨ 1, 2, 3 ⟩$ and confirm that it lies between the two.
3. (c)The maximum of $∥ A x ∥$ over the unit sphere is a different number from the maximum of $x^{T} A x$ . Find it, say where it is attained, and explain why it is not $1$ .
Solution
(a) Spot the structure. Halving each cross coefficient $- 4$ to $- 2$ ,
$A = - 1 - 2 - 2 - 2 - 1 - 2 - 2 - 2 - 1 = I - 2 J, J = 111111111 .$
$J$ has rank $1$ , so $0$ is an eigenvalue with a two-dimensional eigenspace, the plane $x + y + z = 0$ ; and every row of $J$ sums to $3$ , so $J ⟨ 1, 1, 1 ⟩ = 3 ⟨ 1, 1, 1 ⟩$ . Since $A = I - 2 J$ has the same eigenvectors with eigenvalues $1 - 2 μ$ , the eigenvalues of $A$ are $1 - 6 = - 5$ on $⟨ 1, 1, 1 ⟩$ and $1 - 0 = 1$ (twice) on the plane $x + y + z = 0$ . Ordered: $λ_{1} = λ_{2} = 1$ , $λ_{3} = - 5$ . Check: $tr A = - 3 = 1 + 1 - 5$ .
(b) Extreme values are eigenvalues. By the Rayleigh theorem, the maximum of $Q$ on the unit sphere is $λ_{1} = 1$ and the minimum is $λ_{3} = - 5$ .
Where attained: the minimum at the unit eigenvectors for $- 5$ , namely $\pm \frac{1}{3} ⟨ 1, 1, 1 ⟩$ . Check: $Q = - 3 \cdot \frac{1}{3} - 4 \cdot 3 \cdot \frac{1}{3} = - 1 - 4 = - 5$ . The maximum is attained at every unit vector in the eigenspace for $1$ — the whole great circle $x + y + z = 0$ , $x^{2} + y^{2} + z^{2} = 1$ — since for such $x$ , $x^{T} A x = x^{T} (1 \cdot x) = 1$ . Nowhere else: in principal coordinates $Q = y_{1}^{2} + y_{2}^{2} - 5 y_{3}^{2}$ with $\sum y_{k}^{2} = 1$ , and this equals $1$ only when $y_{3} = 0$ . Spot check: at $\frac{1}{2} ⟨ 1, 0, - 1 ⟩$ , $Q = - \frac{1}{2} - \frac{1}{2} - 4 \cdot (- \frac{1}{2}) = 1$ .
Rayleigh quotient at $x = ⟨ 1, 2, 3 ⟩$ : $x^{T} A x = - (1 + 4 + 9) - 4 (2 + 3 + 6) = - 14 - 44 = - 58$ and $x^{T} x = 14$ , so
$R (x) = - \frac{58}{14} = - \frac{29}{7} \approx - 4.14,$
which does lie in $[- 5, 1]$ , as the bound $λ_{3} ∥ x ∥^{2} \leq x^{T} A x \leq λ_{1} ∥ x ∥^{2}$ requires.
(c) Lengths see $∣ λ ∣$ , forms see $λ$ . $∥ A x ∥^{2} = (A x)^{T} (A x) = x^{T} A^{T} A x = x^{T} A^{2} x$ , and $A^{2}$ is symmetric with the same eigenvectors as $A$ and eigenvalues $λ_{k}^{2}$ : $25, 1, 1$ . Applying the Rayleigh theorem to $A^{2}$ , the maximum of $∥ A x ∥^{2}$ on the unit sphere is $25$ , so
$∥ x ∥ = 1 max ∥ A x ∥ = 5,$
attained at $\pm \frac{1}{3} ⟨ 1, 1, 1 ⟩$ . Directly: $A ⟨ 1, 1, 1 ⟩ = ⟨ - 5, - 5, - 5 ⟩$ , which has length $53$ , and dividing by $∥ ⟨ 1, 1, 1 ⟩ ∥ = 3$ gives $5$ .
It is not $1$ because the length of $A x$ does not care about the sign of the stretch: the direction $⟨ 1, 1, 1 ⟩$ is scaled by $- 5$ , which makes the form as negative as possible but makes the image as long as possible. The maximum of the form is $λ_{m a x} = 1$ ; the maximum of $∥ A x ∥$ is $max_{k} ∣ λ_{k} ∣ = 5$ , the spectral norm. (For the same reason the minimum of $∥ A x ∥$ on the sphere is $min_{k} ∣ λ_{k} ∣ = 1$ , not $- 5$ .)
9.Computation
Let $A_{k} = 2 k 0 k 2 k 0 k 2$ , where $k$ is a real parameter.
1. (a)Using Sylvester's criterion, find every $k$ for which $A_{k}$ is positive definite.
2. (b)Show that $A_{k}$ is never negative definite, and prove that it is indefinite for every $k$ outside the range found in (a), endpoints excluded. A sign argument with the trace and the determinant is enough.
3. (c)At the endpoint $k = 2$ , write $x^{T} A_{k} x$ as a sum of two squares, deduce that $A_{2}$ is positive semidefinite but not positive definite, and find a nonzero vector at which the form is zero. Explain why that vector had to be an eigenvector, and for which eigenvalue.
Solution
(a) Three leading minors. $det A_{1} = 2 > 0$ for every $k$ . $det A_{2} = 4 - k^{2}$ . Expanding $det A_{3}$ along the first row,
$det A_{k} = 2 (4 - k^{2}) - k (2 k - 0) + 0 = 8 - 4 k^{2} = 4 (2 - k^{2}) .$
Sylvester's criterion asks for all three to be positive: $4 - k^{2} > 0$ and $2 - k^{2} > 0$ . The second implies the first, so $A_{k}$ is positive definite exactly when $k^{2} < 2$ , that is
$- 2 < k < 2 .$
(b) Never negative definite; indefinite outside. A negative definite matrix has every diagonal entry negative, since $a_{ii} = e_{i}^{T} A e_{i}$ . Here $a_{11} = 2 > 0$ for every $k$ , so $A_{k}$ is never negative definite.
Now let $k^{2} > 2$ . Then $det A_{k} = 4 (2 - k^{2}) < 0$ . The determinant is the product of the three (real) eigenvalues, so an odd number of them — one or three — are negative. Three negative eigenvalues would give a negative trace, but $tr A_{k} = 6 > 0$ . So exactly one eigenvalue is negative and at least one is positive, and $A_{k}$ is indefinite: the form takes both signs.
(For the record the eigenvalues are $2$ and $2 \pm 2 k$ , with eigenvectors $⟨ 1, 0, - 1 ⟩$ and $⟨ 1, \pm 2, 1 ⟩$ , which confirms everything above — but the sign argument needed none of that.)
(c) The endpoint. At $k = 2$ ,
$x^{T} A x = 2 x^{2} + 22 x y + 2 y^{2} + 22 yz + 2 z^{2} = (2 x + y)^{2} + (y + 2 z)^{2},$
as expanding the right-hand side confirms: $2 x^{2} + 22 x y + y^{2} + y^{2} + 22 yz + 2 z^{2}$ . A sum of squares is never negative, so $A_{2}$ is positive semidefinite. It is not positive definite because the sum vanishes at a nonzero vector: both squares are zero when $y = - 2 x$ and $y = - 2 z$ , for instance at
$v = ⟨ 1, - 2, 1 ⟩ .$
Why $v$ must be an eigenvector: by the Rayleigh theorem the minimum of the form over unit vectors is $λ_{m i n}$ , which is $\geq 0$ here since the form is never negative; the unit vector $v /∥ v ∥$ gives the value $0$ , so $λ_{m i n} = 0$ and $v$ attains the minimum. In principal coordinates the form is $\sum λ_{k} y_{k}^{2}$ , and it can equal $λ_{m i n}$ only if all the weight sits on eigenvalues equal to $λ_{m i n}$ — so $v$ lies in the eigenspace for $λ = 0$ . Direct check:
$A_{2} v = ⟨ 2 - 2, 2 - 22 + 2, - 2 + 2 ⟩ = 0 .$
This is consistent with $det A_{2} = 0$ : at the threshold one eigenvalue is exactly zero, which is what Sylvester's criterion failing by equality, rather than by sign, means.
10.Computation
Let $A = 93 - 6 350 - 6 014$ and $b = ⟨ 9, 13, 8 ⟩$ .
1. (a)Compute the Cholesky factor $L$ of $A$ , column by column, and verify $L L^{T} = A$ . What does the success of the algorithm tell you about $A$ , and by which theorem?
2. (b)Solve $A x = b$ using only $L$ : two triangular solves and no elimination on $A$ itself.
3. (c)Read off the pivots of $A$ and $det A$ from $L$ . Then show, using the trace, that the pivots are not the eigenvalues of $A$ , and say which single quantity the pivots and the eigenvalues do share.
4. (d)Replace the entry $14$ by a parameter $t$ . For which $t$ does the Cholesky algorithm succeed? Interpret the threshold value of $t$ in terms of definiteness, and identify the quantity under the final square root as a Schur complement.
Solution
(a) Column by column. Column $1$ : $ℓ_{11} = 9 = 3$ , then $ℓ_{21} = 3/3 = 1$ and $ℓ_{31} = - 6/3 = - 2$ .
Column $2$ : $ℓ_{22} = a_{22} - ℓ_{21}^{2} = 5 - 1 = 2$ , then
$ℓ_{32} = \frac{a _{32} - ℓ _{31} ℓ _{21}}{ℓ _{22}} = \frac{0 - ( - 2 ) ( 1 )}{2} = 1.$
Column $3$ : $ℓ_{33} = a_{33} - ℓ_{31}^{2} - ℓ_{32}^{2} = 14 - 4 - 1 = 3$ .
$L = 31 - 2 021003, L L^{T} = 93 - 6 3 1 + 4 - 2 + 2 - 6 - 2 + 2 4 + 1 + 9 = 93 - 6 350 - 6 014 = A .$
Every quantity under a square root was positive, so the algorithm produced a lower-triangular $L$ with positive diagonal. By the Cholesky theorem — a symmetric matrix is positive definite if and only if it factors as $L L^{T}$ with such an $L$ — $A$ is positive definite.
(b) Two triangular solves. Since $A = L L^{T}$ , solve $L y = b$ forwards and then $L^{T} x = y$ backwards.
Forward: $3 y_{1} = 9$ gives $y_{1} = 3$ ; $y_{1} + 2 y_{2} = 13$ gives $y_{2} = 5$ ; $- 2 y_{1} + y_{2} + 3 y_{3} = 8$ gives $- 6 + 5 + 3 y_{3} = 8$ , so $y_{3} = 3$ . Thus $y = ⟨ 3, 5, 3 ⟩$ .
Backward, with $L^{T} = 300120 - 2 13$ : $3 x_{3} = 3$ gives $x_{3} = 1$ ; $2 x_{2} + x_{3} = 5$ gives $x_{2} = 2$ ; $3 x_{1} + x_{2} - 2 x_{3} = 3$ gives $3 x_{1} = 3$ , so $x_{1} = 1$ . Hence
$x = ⟨ 1, 2, 1 ⟩ .$
Check against $A$ directly: $A x = ⟨ 9 + 6 - 6, 3 + 10 + 0, - 6 + 0 + 14 ⟩ = ⟨ 9, 13, 8 ⟩ = b$ .
(c) Pivots and determinant. The Cholesky diagonal holds the square roots of the pivots, so the pivots are $ℓ_{kk}^{2} = 9, 4, 9$ , and
$det A = (det L)^{2} = (3 \cdot 2 \cdot 3)^{2} = 1 8^{2} = 324,$
equivalently the product of the pivots, $9 \cdot 4 \cdot 9 = 324$ . (Direct check: $det A = 9 (70 - 0) - 3 (42 - 0) + (- 6) (0 + 30) = 630 - 126 - 180 = 324$ .) The leading minors $9$ , $45 - 9 = 36$ , $324$ confirm the pivot ratios $9$ , $36/9 = 4$ , $324/36 = 9$ .
The pivots are not the eigenvalues: the eigenvalues sum to $tr A = 9 + 5 + 14 = 28$ , whereas the pivots sum to $22$ . What the two triples share is their product: both multiply to $det A = 324$ . (All three eigenvalues are positive too, but they are the roots of a cubic that does not factor nicely, and nothing here needs them.)
(d) The threshold. Columns $1$ and $2$ do not involve $a_{33}$ , so $ℓ_{11}, ℓ_{21}, ℓ_{31}, ℓ_{22}, ℓ_{32}$ are unchanged, and the last step becomes $ℓ_{33} = t - 4 - 1 = t - 5$ . The algorithm succeeds exactly when $t > 5$ .
Interpretation: $det A_{t} = 9 \cdot 4 \cdot (t - 5) = 36 (t - 5)$ , while the first two leading minors stay $9$ and $36$ . For $t > 5$ all three are positive and $A_{t}$ is positive definite; at $t = 5$ the matrix is singular with the form still $\geq 0$ — positive semidefinite, and Cholesky fails by hitting $0$ (a zero on the diagonal is not allowed); for $t < 5$ the determinant is negative, so an odd number of eigenvalues are negative, while $a_{11} = 9 > 0$ rules out all three being negative; hence $A_{t}$ is indefinite.
Schur complement: the number $t - 5$ is $a_{33} - v^{T} A_{2}^{- 1} v$ , where $A_{2} = (9335)$ is the leading $2 \times 2$ block and $v = ⟨ - 6, 0 ⟩$ is the rest of the third column. Indeed $A_{2}^{- 1} = \frac{1}{36} (5 - 3 - 3 9)$ and $v^{T} A_{2}^{- 1} v = \frac{1}{36} \cdot 5 \cdot 36 = 5$ . The final pivot is always the Schur complement of the block above it, and positive definiteness of $A_{t}$ is exactly positive definiteness of $A_{2}$ together with positivity of that complement.
11.Proof
Throughout, $A$ is a real symmetric $n \times n$ matrix with eigenvalues $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ and an orthonormal eigenbasis $q_{1}, \dots, q_{n}$ . You may quote the Spectral Theorem and the Rayleigh bounds $λ_{n} ∥ x ∥^{2} \leq x^{T} A x \leq λ_{1} ∥ x ∥^{2}$ .
1. (a)Prove that every diagonal entry satisfies $λ_{n} \leq a_{ii} \leq λ_{1}$ .
2. (b)Prove that if a unit vector $x$ attains the maximum, $x^{T} A x = λ_{1}$ , then $x$ is an eigenvector: $A x = λ_{1} x$ . (Write $x = Q y$ and examine exactly when a weighted average of the eigenvalues can equal the largest of them.)
3. (c)Deduce that if $a_{11} = λ_{1}$ , then every other entry of the first row and of the first column of $A$ is zero.
4. (d)Now let $B$ be a positive semidefinite matrix with some diagonal entry $b_{ii} = 0$ . Prove that the entire $i$ -th row and $i$ -th column of $B$ are zero.
Solution
(a) Test the form on a standard basis vector. $a_{ii} = e_{i}^{T} A e_{i}$ , because $A e_{i}$ is the $i$ -th column of $A$ and dotting with $e_{i}$ picks out its $i$ -th entry. Since $∥ e_{i} ∥ = 1$ , the Rayleigh bounds give $λ_{n} \leq e_{i}^{T} A e_{i} \leq λ_{1}$ . $■$
(b) When does an average equal the maximum? Let $Q = [q_{1} \dots q_{n}]$ , orthogonal by the Spectral Theorem, and write $x = Q y$ , so $y = Q^{T} x$ has $∥ y ∥ = ∥ x ∥ = 1$ and $x^{T} A x = y^{T} Λ y = \sum_{k} λ_{k} y_{k}^{2}$ . The hypothesis $x^{T} A x = λ_{1}$ therefore reads
$0 = λ_{1} - k \sum λ_{k} y_{k}^{2} = λ_{1} k \sum y_{k}^{2} - k \sum λ_{k} y_{k}^{2} = k \sum (λ_{1} - λ_{k}) y_{k}^{2},$
using $\sum_{k} y_{k}^{2} = 1$ . Every term is a product of two nonnegative numbers, so a sum of zero forces every term to be zero: $(λ_{1} - λ_{k}) y_{k}^{2} = 0$ for each $k$ . Hence $y_{k} = 0$ whenever $λ_{k} < λ_{1}$ . Let $S = {k : λ_{k} = λ_{1}}$ ; then $x = \sum_{k \in S} y_{k} q_{k}$ , and
$A x = k \in S \sum y_{k} A q_{k} = k \in S \sum y_{k} λ_{1} q_{k} = λ_{1} x . ■$
(The same argument with $λ_{n}$ in place of $λ_{1}$ shows that a unit vector attaining the minimum is an eigenvector for $λ_{n}$ ; alternatively, apply the result to $- A$ , whose largest eigenvalue is $- λ_{n}$ .)
(c) The first basis vector attains the maximum. If $a_{11} = λ_{1}$ then $e_{1}^{T} A e_{1} = λ_{1}$ with $∥ e_{1} ∥ = 1$ , so by (b) $A e_{1} = λ_{1} e_{1}$ . But $A e_{1}$ is the first column of $A$ ; so the first column is $⟨ λ_{1}, 0, \dots, 0 ⟩$ , i.e. $a_{i 1} = 0$ for all $i \geq 2$ . By symmetry $a_{1 i} = a_{i 1} = 0$ , so the first row is zero off the diagonal too. $■$
(d) A zero on the diagonal of a semidefinite matrix. Positive semidefinite means $x^{T} B x \geq 0$ for all $x$ , so in particular the minimum on the unit sphere, $λ_{n} (B)$ , is $\geq 0$ . By (a), $λ_{n} (B) \leq b_{ii} = 0$ . Hence $λ_{n} (B) = 0$ , and $e_{i}$ attains the minimum of the form.
Apply (b) to $- B$ : its largest eigenvalue is $- λ_{n} (B) = 0$ , and $e_{i}^{T} (- B) e_{i} = - b_{ii} = 0$ equals it, so $(- B) e_{i} = 0 \cdot e_{i}$ , that is $B e_{i} = 0$ . The $i$ -th column of $B$ is therefore zero, and by symmetry so is the $i$ -th row. $■$
This is the semidefinite version of the fact that the largest entry of a positive definite matrix sits on the diagonal: for a semidefinite matrix, a zero diagonal entry wipes out its whole row and column, which is why a covariance matrix with a zero variance in some coordinate has zero covariance between that coordinate and every other.
12.Proof
Let $A$ be a positive definite $n \times n$ matrix, let $b \in R^{n}$ , and define $f (x) = \frac{1}{2} x^{T} A x - b^{T} x$ . Put $x^{*} = A^{- 1} b$ .
1. (a)Prove the identity $f (x) - f (x^{*}) = \frac{1}{2} (x - x^{*})^{T} A (x - x^{*})$ by expanding the right-hand side, and say exactly where the symmetry of $A$ is used.
2. (b)Deduce that $x^{*}$ is the unique global minimiser of $f$ and that the minimum value is $- \frac{1}{2} b^{T} A^{- 1} b$ . Explain what this adds to what the second derivative test would tell you.
3. (c)Check with $A = (2 - 1 - 1 2)$ and $b = ⟨ 1, 4 ⟩$ : verify that $A$ is positive definite, find $x^{*}$ , evaluate $f (x^{*})$ directly from the definition of $f$ , and compare with (b).
4. (d)Let $X$ be an $m \times n$ matrix with linearly independent columns and $y \in R^{m}$ . Show that $g (β) = ∥ y - X β ∥^{2}$ equals $2 f (β) + const$ for suitable $A$ and $b$ , verify that this $A$ is positive definite, and conclude that the least-squares problem has a unique solution, given by the normal equations. Where exactly does the independence of the columns enter?
Solution
(a) Expand and compare. Expanding the right-hand side,
$\frac{1}{2} (x - x^{*})^{T} A (x - x^{*}) = \frac{1}{2} x^{T} A x - \frac{1}{2} x^{T} A x^{*} - \frac{1}{2} (x^{*})^{T} A x + \frac{1}{2} (x^{*})^{T} A x^{*} .$
The two middle terms are equal: $x^{T} A x^{*}$ is a $1 \times 1$ matrix, so it equals its transpose $(x^{*})^{T} A^{T} x$ , and this is where symmetry is used — $A^{T} = A$ turns that into $(x^{*})^{T} A x$ . So the middle terms combine to $- x^{T} A x^{*}$ . Now $A x^{*} = b$ , so $x^{T} A x^{*} = x^{T} b = b^{T} x$ and $(x^{*})^{T} A x^{*} = (x^{*})^{T} b = b^{T} x^{*}$ . The right-hand side is therefore
$\frac{1}{2} x^{T} A x - b^{T} x + \frac{1}{2} b^{T} x^{*} = f (x) + \frac{1}{2} b^{T} x^{*} .$
On the other side, $f (x^{*}) = \frac{1}{2} (x^{*})^{T} A x^{*} - b^{T} x^{*} = \frac{1}{2} b^{T} x^{*} - b^{T} x^{*} = - \frac{1}{2} b^{T} x^{*}$ , so $f (x) - f (x^{*}) = f (x) + \frac{1}{2} b^{T} x^{*}$ , which is exactly the expression just found. $■$
(Positive definiteness was also used silently in writing $A^{- 1}$ at all: if $A x = 0$ then $x^{T} A x = 0$ , which forces $x = 0$ , so $A$ is invertible — equivalently, none of its eigenvalues is zero.)
(b) Positive definiteness finishes it. Put $h = x - x^{*}$ . By (a), $f (x) - f (x^{*}) = \frac{1}{2} h^{T} A h$ , which is $> 0$ for every $h \neq = 0$ by the definition of positive definiteness, and $= 0$ only at $h = 0$ . So $f (x) > f (x^{*})$ for every $x \neq = x^{*}$ : $x^{*}$ is the unique global minimiser, and the minimum value is
$f (x^{*}) = - \frac{1}{2} b^{T} x^{*} = - \frac{1}{2} b^{T} A^{- 1} b .$
What this adds: the gradient of $f$ is $A x - b$ and its Hessian is $A$ , so the second derivative test says only that $x^{*}$ is a strict local minimum. The identity in (a) is exact, with no error term, so it upgrades local to global and gives uniqueness and the minimum value for free. (It also shows why $h^{T} A h \geq λ_{m i n} ∥ h ∥^{2}$ matters: $f$ grows at least quadratically away from $x^{*}$ in every direction.)
(c) A worked instance. Leading minors $2 > 0$ and $4 - 1 = 3 > 0$ , so $A$ is positive definite by Sylvester's criterion. $A^{- 1} = \frac{1}{3} (2112)$ , so
$x^{*} = A^{- 1} b = \frac{1}{3} ⟨ 2 + 4, 1 + 8 ⟩ = ⟨ 2, 3 ⟩ .$
(Check: $A ⟨ 2, 3 ⟩ = ⟨ 4 - 3, - 2 + 6 ⟩ = ⟨ 1, 4 ⟩ = b$ .) Directly from the definition, with $x^{T} A x = 2 x_{1}^{2} - 2 x_{1} x_{2} + 2 x_{2}^{2}$ ,
$f (2, 3) = \frac{1}{2} (8 - 12 + 18) - (2 + 12) = 7 - 14 = - 7.$
Formula from (b): $- \frac{1}{2} b^{T} x^{*} = - \frac{1}{2} (1 \cdot 2 + 4 \cdot 3) = - 7$ . They agree, and for instance $f (0, 0) = 0 > - 7$ and $f (1, 1) = \frac{1}{2} (2 - 2 + 2) - 5 = - 4 > - 7$ , as the theorem requires.
(d) Least squares is this problem in disguise. Expand the squared norm:
$g (β) = (y - X β)^{T} (y - X β) = y^{T} y - 2 y^{T} X β + β^{T} X^{T} X β,$
where the two cross terms $y^{T} X β$ and $β^{T} X^{T} y$ were combined because each is the transpose of the other and both are scalars. With $A = X^{T} X$ and $b = X^{T} y$ this is
$g (β) = 2 [\frac{1}{2} β^{T} A β - b^{T} β] + ∥ y ∥^{2} = 2 f (β) + ∥ y ∥^{2} .$
$A = X^{T} X$ is symmetric, and for any $β$ , $β^{T} X^{T} X β = ∥ X β ∥^{2} \geq 0$ , with equality only when $X β = 0$ . Independence of the columns enters exactly here: it says $X β = 0$ only for $β = 0$ , so the form is strictly positive on nonzero vectors and $A$ is positive definite (this is the $B^{T} B$ test for positive definiteness: $B^{T} B$ is positive definite exactly when $B$ has independent columns, here with $B = X$ ).
By (b), $g$ — a positive constant times $f$ plus a constant — has the unique global minimiser $β^{*} = A^{- 1} b = (X^{T} X)^{- 1} X^{T} y$ , which is precisely the solution of the normal equations $X^{T} X β = X^{T} y$ . If the columns were dependent, $X^{T} X$ would be singular (only semidefinite), the identity in (a) could not even be written, and the minimiser would not be unique: adding any $z$ with $X z = 0$ to a minimiser leaves the residual, and hence $g$ , unchanged.

← Back to the question sheet