# QR factorization for a 4x4 tridiagonal symmetric matrix

1. Apr 13, 2016

### pyroknife

1. The problem statement, all variables and given/known data
$$\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.
2. Relevant equations

3. 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.

2. Apr 13, 2016

### 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.

3. Apr 13, 2016

### 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?

Last edited: Apr 13, 2016
4. Apr 13, 2016

### pyroknife

5. Apr 13, 2016

### andrewkirk

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?