sysmetric tridiagonal matrix

Quote:

Originally Posted by tinng

For the following symmetric matrix A, find a symmetric tridiagonal matrix T, such that A and T have the same eigenvalues.

$A=\begin{bmatrix}2&1&0&0\\ 1&1&2&2\\ 0&2&0&-1\\ 0&2&-1&4\end{bmatrix}$

I suspect that you're meant to do this using Householder's method. Notice that the only things that stop A from being already tridiagonal are the 2s at the bottom of the second column and the end of the second row. We somehow have to get rid of them.

Start by splitting A into 2×2 blocks: $A = \begin{bmatrix}B&C^{\,\textsc{t}}\\C&D\end{bmatrix }$ , where $B = \begin{bmatrix}2&1\\1&1\end{bmatrix}$ , $C = \begin{bmatrix}0&2\\0&2\end{bmatrix}$ , $D = \begin{bmatrix}0&-1\\-1&4\end{bmatrix}$ .

Let Q be a 2×2 orthogonal matrix, and let P be the 4×4 matrix with 2×2-block decomposition $P = \begin{bmatrix}I&O\\O&Q\end{bmatrix}$ , where I is the identity and the Os are zero matrices. Then P is orthogonal, and

$PAP^{\textsc{t}} = \begin{bmatrix}B&C^{\,\textsc{t}}Q^{\textsc{t}}\\ QC&QDQ^{\textsc{t}}\end{bmatrix}.\qquad(*)$

We need to choose Q so that the bottom right-hand element of QC is 0, or in other words $Q\begin{bmatrix}2\\2\end{bmatrix} = \begin{bmatrix}*\\0\end{bmatrix}$ . In general, this can be done by Householder's method of using reflection matrices. In this case, there is also a straightforward geometric solution, taking Q to be the matrix representing a clockwise rotation through π/4. Then $Q = \begin{bmatrix}1/\sqrt2&1/\sqrt2\\ -1/\sqrt2&1/\sqrt2\end{bmatrix}$ , and $Q\begin{bmatrix}2\\2\end{bmatrix} = \begin{bmatrix}2\sqrt2\\0\end{bmatrix}.$ Plug this into the equation (*), and you get $PAP^{\textsc{t}} = \begin{bmatrix}2&1&0&0\\ 1&1&2\sqrt2&0\\ 0&2\sqrt2&1&2\\ 0&0&2&3\end{bmatrix}.$

That matrix is visibly symmetric and tridiagonal, and it has the same eigenvalues as A because it is orthogonally equivalent to it.