Linear Algebra: Cases When LU Decomposition Is Possible.

Home » When Does A Matrix Not Have An Lu Decomposition » Linear Algebra: Cases When LU Decomposition Is Possible.

Maybe your like

GATE Overflow for GATE CSE
  • Ask
  • Activity
  • Q&A
  • Questions
  • Unanswered
  • Tags
  • Subjects
  • Users
  • Previous Years
  • Blogs
  • All Polls
  • New Blog
  • Exams
Dark Mode asked Nov 18, 2018 5,311 views 4 4 votes I had already visited below link but was unable to grasp it. https://math.stackexchange.com/questions/218770/when-does-a-square-matrix-have-an-lu-decomposition. I made some form of self-analysis, let me know if I am in the correct direction. After working on some problems, I found out that LU decomposition of nxn square matrix is not possible, when we don't have full set of n pivots along the main diagonal. What I do is, I take the input matrix A, try to convert it into Echelon form to obtain U by row transformations and apply reverse row transformations to form the matrix L.Obviously LU should be equal A. Consider below matrix A as $\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$ $R_2=R_2+(-4R_1)$ $\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}$=U Now L should be of form $\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}$=L The first row of L tells, take the first row of U and add with $0^{th}$ multiple of the second row of U to produce the 1st row of A. Second Row of L tells, $4*R_1(of\,U)+R_2(of\,U)=R_2(of\,A)$ And in U I have full set of 2 pivots so LU decomposition was possible. Consider another matrix A= $\begin{bmatrix} 1 & 2 &3 \\ 2 & 4 &5\\ 1&3&4\\ \end{bmatrix}$ Now I try to obtain U using Row transformations $R_2=R_2-2R_1,R_3=R_3-R_1$ $\begin{bmatrix} 1 & 2 &3 \\ 0 & 0 &-1\\ 0&1&1\\ \end{bmatrix}$ The pivot in the second row has disappeared. I can interchange $R_2,R_3$ to fix this but that would also change the structure of matrix L, and I think this matrix does not have LU decomposition. So, what I summarized is that if the matrix on being transformed to U through row reductions, loses a pivot, and if such cannot be fixed without a row shuffle operation, then LU decomposition is not possible. Am I correct?
  • Linear Algebra
  • linear-algebra
  • matrix
+ – User Avatar 368 567 809 5.3k views answer comment Share Follow 🖨️ Print See all 3 Comments

3 3 Comments reply

User Avatar 745 1013 1684 commented Nov 18, 2018 reply Follow flag I donot understand, why u r doing row column elimination in LU 0 0 reply Share User Avatar 368 567 809 commented Nov 18, 2018 reply Follow flag @srestha-My main point I want to ask is when I reduce a matrix A to Echelon form(U), and suppose I loose a pivot in any row while doing so, then that matrix won't be LU factorizable na? 1 1 reply Share User Avatar 1 1 4 commented Nov 24, 2020 reply Follow flag

Refer: https://learn.lboro.ac.uk/archive/olmp/olmp_resources/pages/workbooks_1_50_jan2008/Workbook30/30_3_lu_decmp.pdf

Page 7. there it is explained.

0 0 reply Share

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

2 2 votes

You already found this from Wikipedia but what it means like-

Any square matrix A admits an LUP factorization. If A is invertible, "then it admits an LU (or LDU) factorization if and only if all its leading principal minors are non-zero". If A is a singular matrix of rank k, then it admits an LU factorization if the first k leading principal minors are non-zero, although the converse is not true.

bolded line says that if determinant(minor) of leading principal are non- zero then only a matrix admits LU factorization.

So now according to your examples-

1) $\begin{bmatrix} 2 &1 \\ 8 & 7 \end{bmatrix}$

principal submatrices are $\begin{bmatrix} 2 \end{bmatrix} , \begin{bmatrix} 7 \end{bmatrix}, \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

but leading principal submatrices are $\begin{bmatrix} 2 \end{bmatrix} ,\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

and determinant of all are 2, 6 which are non zero so above matrix admits the LU factorization.

2) $\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

principal submatrices are $\begin{bmatrix} 1 \end{bmatrix} , \begin{bmatrix} 4 \end{bmatrix}, \begin{bmatrix} 4 \end{bmatrix},\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix},\begin{bmatrix} 1 & 3 \\ 1 & 4 \end{bmatrix},\begin{bmatrix} 4 & 5 \\ 3 & 4 \end{bmatrix},\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

but leading principal submatrices are $\begin{bmatrix} 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix},\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

and determinant of 1st leading principal submatrix is 1 and , for 2nd it is 0 which are not non zero so above matrix does not admit the LU factorization.

So yes your statement is correct.

answered Nov 18, 2018 User Avatar 19 35 92 comment Share Follow See 1 comment

1 1 comment reply

User Avatar 9 26 91 commented Oct 17, 2024 reply Follow flag

@Shubhgupta intiutively what do we want to know from "leading principal minors not being 0's". how it's ensuring that we will get to matrix U without swapping rows of matrix A when converting A to U using gaussian elimination ?

0 0 reply Share

Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community ← PreviousNext →← Previous in categoryNext in category →

Related questions

0 0 votes 1 1 answer 412 412 views anujs asked Oct 17, 2024 412 views Resources: LU Decomposition what are some good resources to learn about LU decomposition ? User Avatar anujs 412 views anujs asked Oct 17, 2024
  • Linear Algebra
  • engineering-mathematics
  • linear-algebra
  • lu-decomposition
  • matrix
+ – 8 8 votes 1 answers 1 answer 2.9k 2.9k views Lakshman Bhaiya asked Jan 13, 2018 2,876 views LU decomposition In the LU decomposition of the matrix,$\begin{bmatrix} 1 &2 \\ 3 &8 \end{bmatrix}$ if the diagonal elements of $U$ are both $1$, then the trace of $L$ is$?$ User Avatar Lakshman Bhaiya 2.9k views Lakshman Bhaiya asked Jan 13, 2018
  • Linear Algebra
  • engineering-mathematics
  • linear-algebra
  • matrix
  • lu-decomposition
+ – 2 2 votes 2 2 answers 2.3k 2.3k views Tuhin Dutta asked Dec 10, 2017 2,305 views LU decomposition Given the system of linear equations:$4y\ +\ 3z\ =\ 8\\ 2x\ -\ z\ =\ 2\\ 3x\ +\ 2y\ =\ 5$Find L & U. User Avatar Tuhin Dutta 2.3k views Tuhin Dutta asked Dec 10, 2017
  • Linear Algebra
  • linear-algebra
  • matrix
  • engineering-mathematics
+ – 0 0 votes 1 1 answer 5.8k 5.8k views learncp asked Sep 11, 2015 5,782 views How to calculate LU decomposition of a 2*2 matrix ? I need to calculate determinant of a 2*2 matrix such as$\begin{bmatrix} 2 &2 \\ 4& 9 \end{bmatrix}$I proceeded by making it a upper triangular matrix and then using the n... User Avatar learncp 5.8k views learncp asked Sep 11, 2015
  • Linear Algebra
  • linear-algebra
  • matrix
+ – 📢 Notice Board GATE Overflow Test Series GO Test Series 2026 Purchase link is live now Subscribe to GO Classes for GATE CSE 2026 Online coaching classes by Sachin & Deepak GATE Overflow Timeline Visual history of GO’s journey GATE Overflow FAQ Read about Gateoverflow and how to use it. Hide side panel Seach the website Search UI Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Search For Tags

Match the exact tag

Recent Posts

  • BARC Recruitment of Scientific Officers through GATE Score / Online Exam 2026
  • Introducing Random Quiz / Exam
  • PSU Career Opportunities via GATE 2026
  • Interview Experience: MS by Research in Computer Science – Winter Admission at IIT Madras
  • GATE CSE 2025 Approximate Cut-offs

Subjects

  • All categories
  • General Aptitude (4.8k)
  • Engineering Mathematics (13.3k)
    • Discrete Mathematics (7.9k)
    • Probability (2.1k)
    • Linear Algebra (2.0k)
    • Calculus (1.3k)
    • Optimization (19)
  • Digital Logic (4.1k)
  • Programming and DS (7.1k)
  • Algorithms (5.5k)
  • Theory of Computation (7.6k)
  • Compiler Design (2.7k)
  • Operating System (5.9k)
  • Databases (5.5k)
  • CO & Architecture (4.4k)
  • Computer Networks (5.6k)
  • Artificial Intelligence (281)
  • Machine Learning (1.1k)
  • Data Mining and Warehousing (49)
  • Non GATE CSE (2.0k)
  • Others (6.8k)
  • Admissions (723)
  • Exam Queries (1.6k)
  • Tier 1 Placement Questions (18)
  • Job Queries (90)
  • Projects (28)
  • Unknown Category (547)

Site Statistics

80.1k questions

101k answers

282k comments

288k users

Recent Blog Comments

  • congratulations. was there any criteria for btech...
  • @iamavx, select only the gate2025 paper and...
  • Can You add a feature like we can select random...
  • when is GATE Overflow only full lengt test series...
  • Brother your interview went good then why you...
X WhatsApp Facebook Reddit LinkedIn Email Link Copied! Copy

Tag » When Does A Matrix Not Have An Lu Decomposition