GATE Overflow Test Series | Linear Algebra | Test 1 | Question: 29

Question

$P:$ The matrix $\begin{bmatrix} 0 & 4\\
0 & 5 \end{bmatrix}$ has infinitely many $LU$ factorizations, where $L$ is lower triangular and $U$ is upper triangular with each diagonal entry $1$.
$Q:$ The matrix $\begin{bmatrix} 5 & 4\\
0 & 0 \end{bmatrix}$ has no $LU$ factorization, where $L$ is lower triangular and $U$ is upper triangular with each diagonal entry $1$.
For the given statements $P$ and $Q,$

• A. $P$ is true and $Q$ is false
• B. Both $P$ and $Q$ are true
• C. $P$ is false and $Q$ is true
• D. Both $P$ and $Q$ are false

Answer 1

Any square matrix $A$ admits $LUP$ and $PLU$ factorizations. If $A$ is invertible, then it admits an $LU \;\text{(or)}\; LDU)$ factorization if and only if all its leading principal minors are nonzero. 

$\textbf{(or)}$

An invertible matrix $A$ has an $LU$ decomposition provided that all its leading submatrices have non-zero determinants. The $k^{\text{th}}$ leading submatrix of $A$ is denoted $A_{k}$ and is the $k \times k$ matrix found by looking only at the top $k$ rows and leftmost $k$ columns.

If a square, invertible matrix has an $LDU$ (factorization with all diagonal entries of $L$ and $U$ equal to $1$), then the factorization is unique. In that case, the $LU$ factorization is also unique if we require that the diagonal of $L\; \text{(or)}\;U $ consists of ones.

If $A$ is a singular matrix of rank $k$, then it admits an $LU$ factorization if the first $k$ leading principal minors are nonzero, although the converse is not true.

 Matrix $A_{k \times k}$ has $LU$ factorization if: $$\mathsf Rank(A_{11})+k\geq   Rank\left(\begin{bmatrix}
    A_{11}       & A_{12} 
\end{bmatrix}\right) +Rank\left(\begin{bmatrix}
    A_{11}   \\ A_{21} 
\end{bmatrix}\right)$$

this must hold for each $k = 1,\dots, n − 1.$

We can also write these conditions as $\text{rank}\left(A[{1 \dots k}]\right) + k \geq  \text{rank}\left(A[{1 \dots k}, {1 \dots n}] \right)+ \text{rank}\left(A[{1\dots n}, {1 \dots k}]\right)$ for all $k = 1, \dots , n.$

$P:$ Let $A=\begin{bmatrix} 0&4 \\0 & 5\end{bmatrix} \implies \det(A) = 0\quad \text{(Singular matrix)}$

Here, $\text{rank}(A) = 1,$ and first leading principal minor are $0.$

Hence, LU-factorization is not possible.

$Q:$ Let $B=\begin{bmatrix} 5&4 \\0 & 0\end{bmatrix} \implies \det(B) = 0 \quad \text{(Singular matrix)}$

Here, $\text{rank}(B) = 1,$ and first leading principal minor are $5.$

Hence, $LU$-factorization is possible.

$\therefore$ Both $P$ and $Q$ are false.

So, the correct answer is $(D).$

Reference: 

• https://arxiv.org/pdf/math/0506382v1.pdf
• https://en.wikipedia.org/wiki/LU_decomposition#Existence_and_uniqueness
• https://web.archive.org/web/20201021202811/https://learn.lboro.ac.uk/archive/olmp/olmp_resources/pages/workbooks_1_50_jan2008/Workbook30/30_3_lu_decmp.pdf

Comments

$\bigl(\begin{smallmatrix} 5 & 4 \\ 0 & 0 \end{smallmatrix}\bigr)=\bigl(\begin{smallmatrix} l11 & 0 \\ l21 & l22 \end{smallmatrix}\bigr).\bigl(\begin{smallmatrix} u11 & u12 \\ 0 & u22 \end{smallmatrix}\bigr)$

 

l11u11=5...(i)

l11u12=4...(ii)

l21u11=0...(iii)

l21u12+l22u22=0..(iv)

$l11\neq 0  $

$ u11\neq 0$

From (iii) since u11 is not zero so l21=0 and

Now considering equation (iv) first term l21u12=0

For second term l22u22 =0 , either l22=0 or u22=0. Now since given u11=u22=1

So surely l22=0.

So proposed L matrix is like $\bigl(\begin{smallmatrix} l11 &0 \\ 0&0 \end{smallmatrix}\bigr)$

According to general theorem L and U would have to be invertible or determinant of L must not be 0.

Here it is coming 0. So the statement Q should be true. Am I doing anything wrong?

---

If a matrix A Is singular then even if we have non zero principal minor, LU decomposition is not possible

Q is true.

---

Ithink OPtion C is correct.

---

If A is a singular matrix of rank k, then it admits an LU factorization if the first k leading principal minors are nonzero, although the converse is not true.

Matrix given in $Q$ has rank 1, so if the first 1 leading sub matrices have non-zero determinant, it will have LU decomposition. We can see, the first leading submatrix has non-zero determinant = 5. Hence, it has a LU decomposition. So, Q is also false.