If A ∈ R n × n is singular and x , b ∈ R n are such that A x = b, am I right in thinking that the upper triangular matrix R of A's Q R decomposition must have at least one diagonal entry because otherwise saying R x = Q T b and using backward substitution would give one definite answer for x. But, because A is singular, there cannot be just one solution to the system?

Question

If   A  ∈        R          n      ×      n       is singular and   x  ,  b  ∈        R      n   are such that   A  x  =  b, am I right in thinking that the upper triangular matrix   R of   A&#039;s   Q  R decomposition must have at least one diagonal entry because otherwise saying   R  x  =      Q      T    b and using backward substitution would give one definite answer for   x. But, because   A is singular, there cannot be just one solution to the system?

Odin Jacobson · Accepted Answer

If your matrix   A is singular, then you can use the pivoted   Q  R factorisation:  A  Π  =  Q  R  ,where   Π is a permutation matrix,   Q is square orthogonal and the triangular   R has the block form  R  =      [                                        R                      11                                                R                      12                                                0                          0                      ]    ,where       R      11    ∈        R          r      ×      r       (  r is the rank of   A) is nonsingular and upper triangular. Then   A  x  =  b is equivalent to  R      x    ~    =      b    ~    ,        x    ~    =      Π    T    x  ,        b    ~    =      Q    T    b  .Using the partitioning       x    ~    =  [              x      ~        1    T    ,              x      ~        2    T        ]    T   and       b    ~    =  [              b      ~        1    T    ,              b      ~        2    T        ]    T   leads to      R      11                x      ~        1    +      R      12                x      ~        2    =              b      ~        1    ,    0  =              b      ~        2    .So, the system is solvable iff               b      ~        2    =  0 and any solution   x can be obtained by choosing an arbitrary vector               x      ~        2  , solving       R      11                x      ~        1    =              b      ~        1    −      R      12                x      ~        2  , and performing the permutation   x  =  Π      x    ~  . You might want to obtain, e.g., the minimum 2-norm solution, which can be done simply by choosing               x      ~        2    =  0.Note that the   Q  R decomposition can be less numerically reliable for solving rank-deficient problems than the SVD, or, more precisely, the truncated SVD approach.

If A ∈ <mi mathvariant="double-struck">R n &#

Answered question

Answer & Explanation

New Questions in Algebra I