2

$$\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} $$ I am trying to solve the following problem: For the given 4x4 symmetric tridiagonal matrix A, determine which elements of its QR factorization is zero. The trick is to determine this visually.

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.

roulette01
  • 403

1 Answers1

1

I will show you how to obtain some zeros and you should be able to continue by yourself. Consider the first column of $R$.You have $q_{11}r_{11}=a_{11}$, $q_{21}r_{11}=a_{12}$, $q_{31}r_{11}=0$ and $q_{41}r_{11}=0$. If $a_{11}$ or $a_{12}$ is not $0$, then you have necessarely that $r_{11} \neq 0$, and so you have $q_{31}=0$ and $q_{41}=0$.You can try to do the same kind of reasoning on the following column of $R$ for example.

Bérénice
  • 9,367
  • Thanks a lot that makes sense. One question though: if $a_{11}$ and/or $a_{12}$ is 0, is the A matrix still tridiagonal? – roulette01 Apr 13 '16 at 16:46
  • I think that tridiagonal means that $a_{ij}=0$, $\forall i,j$ such as $|i-j|>1$. But in your case it is propably assume the other elements are not $0$, otherwise you could not know a lot of things visually. – Bérénice Apr 13 '16 at 16:59
  • Yes, that is what I'm thinking. Otherwise, the solution would not be unique. – roulette01 Apr 13 '16 at 17:17
  • For the second column of R, I obtain \begin{equation} q_{11}r_{12} + q_{12}r_{22} = a_{12} \end{equation} \begin{equation} q_{21}r_{12} + q_{22}r_{22} = a_{22} \end{equation} \begin{equation} q_{32}r_{22} = a_{23} \end{equation} \begin{equation} q_{42}r_{22} = 0 \end{equation} looking at the last 2 expressions, we can see that $r_{22}$ and $q_{32}$ are non-zero and $q_{42}$ is 0, but this doesn't seem to say anything about $q_{12}$ and $q_{22}$? – roulette01 Apr 13 '16 at 18:51
  • Yes that's it :). – Bérénice Apr 13 '16 at 18:57
  • But how would we know if $q_{12}$ and $q_{22}$ are non-zero? It seems this would depend on specific case we are talking about. – roulette01 Apr 13 '16 at 19:05
  • You can't know that, you can't have every informations about about all the elements of Q in such a general case. – Bérénice Apr 13 '16 at 19:08
  • Ah yes, I see. I know that $r_{14} = 0$, but this process doesn't seem to conclude that? – roulette01 Apr 13 '16 at 19:12
  • I don't see how to find this other result sorry. – Bérénice Apr 13 '16 at 19:30