Skip to content

6.3-final-2008-strang

Final Exam, 2008 (strang) · Section 6.3: Symmetric Positive Definite Matrices Source: finalexam_1.pdf, p. 210

Problem

3 (12 pts.) Two eigenvalues of this matrix \(A\) are \(\lambda_1 = 1\) and \(\lambda_2 = 2\). The first two pivots are \(d_1 = d_2 = 1\).

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

(a) Find the other eigenvalue \(\lambda_3\) and the other pivot \(d_3\).

(b) What is the smallest entry \(a_{33}\) in the southeast corner that would make \(A\) positive semidefinite? What is the smallest \(c\) so that \(A + cI\) is positive semidefinite?

(c) Starting with one of these vectors \(u_0 = (3, 0, 0)\) or \((0, 3, 0)\) or \((0, 0, 3)\), and solving \(u_{k+1} = \frac{1}{2}Au_k\), describe the limit behavior of \(u_k\) as \(k \to \infty\) (with numbers).

Solution (a) The sum of the eigenvalues is the trace, so \(1 + 2 + \lambda_3 = 2\). Thus \(\lambda_3 = -1\). The product of the pivots is the determinant, which is the product of the eigenvalues as well. So \(d_3 = -2\). Note that this means that \(A\) is not positive-definite. (b) We can test positive-definiteness using the determinant method. The two top-left determinants of \(A\) are both positive, so we just need to check the third one. We obtain the relation \[ 1(c - 1) + 1(-1) \geq 0, \] so the smallest value of \(c\) is 2. For the second part, we test whether the eigenvalues are non-negative. The eigenvalues of \(A + cI\) are just the eigenvalues of \(A\) plus \(c\). So when \(c = 1\) all the eigenvalues will be non-negative. (c) The matrix \(\frac{1}{2}A\) is a Markov matrix. Because it has some 0 entries, we don't automatically know that it has a unique steady state vector. However, since the eigenvalues of \(\frac{1}{2}A\) are 1/2, -1/2 and 1, it does have a unique steady state vector (only one eigenvalue has absolute value 1). To find it, we calculate the eigenvector of \(A\) with eigenvalue 2 by taking the nullspace of \(A - 2I\): \[ A - 2I = \begin{bmatrix} -1 & 0 & 1 \\ 0 & -1 & 1 \\ 1 & 1 & -2 \end{bmatrix} \rightsquigarrow \begin{bmatrix} -1 & 0 & 1 \\ 0 & -1 & 1 \\ 0 & 0 & 0 \end{bmatrix}. \] The nullspace is generated by the special solution \((1, 1, 1)\). So, a vector \(u\) will have limit \(A^{\infty}u\) equal to \(c(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})\), where \(c\) is the sum of the components of \(u\). In particular, the vectors \((3, 0, 0)\), etc., all go to \((1, 1, 1)\).

Keywords: eigenvalues, pivots, positive semidefinite, Markov matrix