QR factorization for a 4x4 tridiagonal symmetric matrix

[pyroknife]

Homework Statement

$$\begin{bmatrix}
a_{11} & a_{12} & 0 & 0\\
a_{12} & a_{22} & a_{23} & 0\\
0 & a_{23} & a_{33} & a_{34} \\
0 & 0 & a_{34} & a_{44} \\
\end{bmatrix}
=
\begin{bmatrix}
q_{11} & q_{12} & q_{13} & q_{14} \\
q_{21} & q_{22} & q_{23} & q_{24} \\
q_{31} & q_{32} & q_{33} & q_{34} \\
q_{41} & q_{42} & q_{43} & q_{44} \\
\end{bmatrix}
\begin{bmatrix}
r_{11} & r_{12} & r_{13} & r_{14} \\
0 & r_{22} & r_{23} & r_{24} \\
0 & 0 & r_{33} & r_{34} \\
0 & 0 & 0 & r_{44} \\
\end{bmatrix}
$$

For the given 4x4 symmetric tridiagonal matrix A, determine which elements of its QR factorization is zero. The trick is to determine this visually.

Homework Equations

The Attempt at a Solution

I plugged a simple 4x4 symmetric tridagonal matrix into MATLAB and took its qr factorization and found that the top left element, $r_{14}$ of the matrix R and the bottom left 3 elements, $q_{31}, q_{41}, q_{42}$ of the matrix Q are zero. But the task was to determine this with ease and visually. Is there a trick to do this? I am not seeing it.

 

[andrewkirk]

If we look at the process for factorising, we see that the $j$th entry in the top row of the R triangular matrix is proportional to $\langle a_1,a_j\rangle$, where $a_j$ is the $j$th column of the original matrix $A$. For $j=4$ that inner product must be zero because the first two components of $a_1$ and the last two components of $a_4$ are zero.

 

[pyroknife]

If we look at the process for factorising, we see that the $j$th entry in the top row of the R triangular matrix is proportional to $\langle a_1,a_j\rangle$, where $a_j$ is the $j$th column of the original matrix $A$. For $j=4$ that inner product must be zero because the first two components of $a_1$ and the last two components of $a_4$ are zero.

Ahh thanks I see this. But what if some of the elements in the original matrix $A$ along the tridiagonal band are zero? This still seems to fit the definition of a tridiagonal matrix? But if, say, $a_{11}$ was 0, then the solution is not unique?

And also, how does your process apply to the elements of Q, and to rows 2-4 of matrix R?

 

[pyroknife]

Ahh thanks I see this. But what if some of the elements in the original matrix $A$ along the tridiagonal band are zero? This still seems to fit the definition of a tridiagonal matrix? But if, say, $a_{11}$ was 0, then the solution is not unique?

And also, how does your process apply to the elements of Q, and to rows 2-4 of matrix R?
Edit: you mean $j$th entry in the top row of the R triangular matrix is proportional to $\langle q_1,a_j\rangle$ right?

 

[andrewkirk]

Ahh thanks I see this. But what if some of the elements in the original matrix $A$ along the tridiagonal band are zero? This still seems to fit the definition of a tridiagonal matrix? But if, say, $a_{11}$ was 0, then the solution is not unique?

And also, how does your process apply to the elements of Q, and to rows 2-4 of matrix R?

Looking at the process as set out here, we see that the expression of an element of R in terms of columns of A is only simple in the first row. So I think it would be hard to visually predict zeros in other rows of R. It would be possible, but would require thinking several steps ahead (probably beyond me, without a paper and pencil).

If there were other zeros in the tridiag band, one could visually predict. For instance, if $a_{23}=0$ then we know that $r_{13}$ will be zero because $\langle a_1,a_3\rangle=0$. Ditto for $r_{12}$ if $a_{12}=a_{22}=0$. So the method is fairly limited in scope. I doubt that there is a visual method that can get any further than that. Since your MatLab result shows that there is only one zero to be found, perhaps your lecturer doesn't believe there is any more general method either. After all, if these things could be completely determined visually, why would there be a need for an algorithm?