1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

QR factorization for a 4x4 tridiagonal symmetric matrix

  1. Apr 13, 2016 #1
    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. jcsd
  3. Apr 13, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Apr 13, 2016 #3
    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
  5. Apr 13, 2016 #4
     
  6. Apr 13, 2016 #5

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: QR factorization for a 4x4 tridiagonal symmetric matrix
Loading...