How can we use Householder's method to place the following matrix in tridiagonal form?
$$A =\pmatrix{4 & -1 & -1 & 0 \\ -1 & 4 & 0 & -1 \\ -1 & 0 & 4 & -1 \\ 0 & -1 & -1 & 4} $$
Basically, I'm stuck on understanding the method and am trying to understand how to do it with this matrix. Thanks
So I can only really understand of getting S and R from column 1
Rewrite your matrix as $$ A=\begin{pmatrix}4&u^T\\ u&\ast\end{pmatrix}, $$ where $u^T=(-1,-1,0)$. Let $Q_3$ be the 3-by-3 Householder matrix whose first column is $u/\|u\|$ (please review your lecture notes or textbook to see how to construct such a matrix $Q_3$). Then $$ A':=\begin{pmatrix}1\\ &Q_3^T\end{pmatrix}A\begin{pmatrix}1\\ &Q_3\end{pmatrix}=\begin{pmatrix}4&\begin{array}{c}\|u\|&0&0\end{array}\\ \begin{array}{c}\|u\|\\0\\ 0\end{array}&\Large B\end{pmatrix}. $$ In other words, we use a Householder matrix to zero out all but the first two entries in the first row and first column of $A$. Then you may proceed recursively. However, since $A$ is only 4-by-4 in this example, we need only one more iteration. Let $$ B=\begin{pmatrix}\ast&v^T\\ v&\ast\end{pmatrix}, $$ where $v$ is a $2$-vector. Find a 2-by-2 Householder matrix $Q_2$ whose first column is $v/\|v\|$. Then $$ \begin{pmatrix}1\\&Q_2^T\end{pmatrix}B\begin{pmatrix}1\\&Q_2^T\end{pmatrix}=\begin{pmatrix}\ast&\|v\|&0\\ \|v\|&\ast&\ast\\0&\ast&\ast\end{pmatrix}. $$ Again, we use a Householder matrix to zero out all except the first two entries in the first row and first column of $B$. Now $$ A'':=\begin{pmatrix}1\\&1\\&&Q_2^T\end{pmatrix}A'\begin{pmatrix}1\\&1\\&&Q_2^T\end{pmatrix}=\begin{pmatrix}4&\|u\|&0&0\\ \|u\|&\ast&\|v\|&0\\ 0&\|v\|&\ast&\ast\\0&0&\ast&\ast\end{pmatrix} $$ is tridiagonal.
You can always use the Householder method to tridiagonalize a matrix. Basically the Householder transformation is doing this:
I think it is the best if you write where you started with the algorithm of doing this and then I can help you.
