Questions tagged [lu-decomposition]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
56 views

Cost of LU decomposition

We consider a matrix $A \in \mathbb R^{2n \times 2n}$ of the form $$A= \begin{bmatrix} D & B \\ C & Â \end{bmatrix}$$ where $D \in \mathbb R^{n \times n}$ is diagonal and $B,C, Â \in\mathbb R^...
0
votes
0answers
18 views

Solving $Ax=b$ from $A=LDU$ decomposition

Suppose a matrix $A \in \mathbb{R}^{n \times n}$ is decomposed into $A = LDU$ where $L$ is a lower triangular matrix, $U$ is an upper triangular matrix, and $D$ is a diagonal matrix. What would be the ...
1
vote
1answer
33 views

DU decomposition

My professor said that we can't express a square matrix as a product of upper triangular matrix and lower triangular although it can be expressed as a product of lower triangle matrix and an upper ...
1
vote
0answers
33 views

Example of regular tridiagonal matrix $A$ with given properties

I am looking for a regular tridiagonal matrix $A$ such that at the LU-decomposition with partial column pivoting the matrices $L$ and $U$ are also tridiagonal, but with total pivoting the matrices $L$ ...
2
votes
2answers
69 views

Calculate the LU-decomposition $PA=LU$ : How do we calulate $L$?

Calculate the LU-decomposition $PA=LU$ for the matrix $$A=\begin{pmatrix}3 & 1 & -3 & 2 \\ -2 & 1 & 0 & 0 \\ 2 & -2 & 4 & 1 \\ 0 & -1 & -1 & 3\end{...
0
votes
1answer
23 views

Understanding the proof the iterative improvement method for the result of linear equation solving using LU decomposition in numerical recipes

The question is from section 2.5 Iterative Improvement of a Solution to Linear Equations in Numerical Recipes book. When we solve $\mathbf{Ax = b}$ using LU decomposition numerically, the result is ...
0
votes
0answers
22 views

Shouldn't all values in pivot positions be nonzero in LU decomposition?

I solved a problem which asked "in what cases is LU decomposition of the given matrix possible?". After the elimination, I got the following matrix: $\begin{bmatrix} 1 & 0 & 1\\ 0 &...
1
vote
1answer
40 views

Proving by induction that $L = I + \sum_{ k=1}^{n-1} u ^{(k)} e ^T _k $

Let $L = \prod_{k=1}^{n-1}(I + u^{(k)}e^T_k) $ where $u^{(k)} (i) = 0$ for $i = 1 : k$. Prove that $L = I + \sum_{k=1}^{n-1}u^{(k)} e^T_k$ by induction. (where $L$ is the lower triangular matrix of ...
0
votes
1answer
20 views

Unit lower triangular matrices multiplication

We know that product of two unit lower triangular matrices is a unit lower triangular matrix. However, if product of two lower triangular matrices is unit lower triangular then is it necessary for the ...
0
votes
0answers
26 views

Determining the permutation matrix

In Python using the la.lu_factor(A) function you get one of the outputs to be piv which is supposed to represent the pivot rows for the permutation matrix but I'm not sure how to determine the actual ...
0
votes
1answer
61 views

Counter example of LU decomposition uniqueness

LU decomposition Theorem: If $A \in \mathbb{R}^{n \times n}$ is such that each principal minor $A_k$ has $det(A_k) \neq 0, \, k = 1, 2, \dots, n-1$, then $A = LU$, beeing $L$ a lower triangular unit ...
1
vote
2answers
98 views

How to switch rows in matrix L when decomposing matrix A into PA = LU?

Find the permutation matrix $P$, the lower triangular matrix $L$ and the upper triangular matrix $U$ such that $$ PA=LU $$ Given $$ A= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ -2 ...
0
votes
1answer
40 views

Diagonal entries of $U$ in $LU$ factorisation of positive definite matrix

Let $A\in M(n,\mathbb R)$ be a symmetric positive definite matrix. Let $L$ be a lower triangular matrix with real entries, all whose diagonal entries are $1$ and $LA$ is upper triangular. Then, is it ...
0
votes
1answer
65 views

Finding the LU decomposition of a matrix using the shortcut method

I was asked to find the LU decomposition of $$\begin{bmatrix}5&4\\-2&-3\\\end{bmatrix}$$ I know that the shortcut method means finding the upper and using the multiplier to find the lower. In ...
0
votes
1answer
39 views

Calculate number of eigenvalues in interval $[-2, 3>$ of matrix $A$ using Sylvesters law of inertia and $LDL^T$ decomposition.

I have a new one, and I am not sure about a few things. I hoped you might help me in understanding them. For matrix $$ A=\left[ \begin{matrix} 4 & 4 & 0 \\ 4 & 6 & 2 \\ 0 & 2 & ...
8
votes
1answer
134 views

Is $A$ ill conditioned matrix?

Suppose we have a matrix $A$ with is its $LU$-decomposition such that $A=LU$ and suppose that $U$ is ill conditioned ($\left \| U \right \|\left \| U^{-1} \right \|$ is large) , does it mean that $A$ ...
0
votes
2answers
236 views

Is the permutation matrix P of PLU decomposition unique?

Let $A$ be a square matrix. Then there exists a permutation matrix $P$ such that $A=PLU$, where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix. To further ensure the uniqueness,...
3
votes
1answer
79 views

$PA = LU$ decomposition

Consider a matrix $A= \begin{pmatrix} 1 & 2 & 1\\ 3 & 6 & 1\\ 0 & 4 & 1 \end{pmatrix}$ I am applying the transformations on matrix $A$ to convert it to $U$ using the ...
5
votes
1answer
104 views

Solve many linear equations of similar structure

Given G: real and symmetric square matrix v: real column vector I need to solve n linear systems of the form \begin{align} A = \begin{pmatrix} G & v \\\ v^T & 0 \end{pmatrix}\end{align} \...
3
votes
1answer
83 views

Is a symmetric matrix positive definite iff $D$ in its LDU decomposition is positive definite?

Given $$A=LDU$$ where $A$ is a real symmetric matrix $L$ is a lower unitriangular matrix $D$ is a diagonal matrix $U$ is an upper unitriangular matrix can we say that $$A>0 \iff D>0$$ ? Edit:...
0
votes
2answers
247 views

Determining whether a matrix is positive definite from its LU decomposition

Given that $A=LU$ where $L$ and $U$ are (known) lower and upper triangular matrices, is there any simple way to determine whether $A$ is positive definite? Background I have been using this algorithm ...
0
votes
3answers
294 views

Given A=LU factorization, prove that the basis of column space A is the columns of L that correspond to the pivot columns of U

I understand that the basis of column space A is just the columns of A that correspond to the pivot columns of U. This is because U is just the reduced row echelon form. However, as mentioned in the ...
1
vote
2answers
40 views

Finding a matrix that can be represented with only single LU decomposition

I'm trying to disprove the following statement: Let $M$ be a singular matrix $3\times 3$ that can be represented with LU decomposition ($M=LU$), then the decomposition is unique (only one ...
0
votes
0answers
18 views

$PA=LU$ decomposition for the special matrix

The cost of decomposition $LU=PA$ for the matrix $A_{N\times N}$ is $O(N^3)$. However if we know about some special properties of matrix $A$ then we can reduce this cost but I wonder how to do it. In ...
0
votes
1answer
66 views

Showing $LU$ is impossible… [closed]

Show that $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=LU$ is impossible where $L$ is lower triangular and $U$ is upper triangular.
0
votes
0answers
18 views

Precomputing the permutation matrix in LUP decomposition

Let $A$ be a dense $n\times n$ matrix and $P$ be the row permutation matrix from the LU decomposition $PA = LU$. Are there any fast algorithms, i.e. faster than $O(n^3)$, for computing a $P$ that ...
0
votes
1answer
73 views

How to prove that LU decomposition is unique?

given the following matrix how could I prove that LU decomposition of it is unique? A= 1 3 1 2 9 2 1 3 1 L= 1 0 0 2 1 0 1 0 1 U= 1 3 1 0 3 0 0 0 0
0
votes
1answer
100 views

proving that lu decomposition is not unique on singular matrix.

How to prove that the following isn't true (using 3 by 3 matrix): Given A is a square and a singular matrix (which means non invertible), if LU decomposition is possible without the use of ...
0
votes
1answer
60 views

How can I find an LU factorisation of this $3 \times 3$ matrix?

$$A=\begin{bmatrix}1&2&-3\\-2&-4&8\\-3&-4&14\end{bmatrix}$$ This is what I found: $$U=\begin{bmatrix}1&2&-3\\0&0&2\\0&0&8\end{bmatrix}$$ $$L=\begin{...
0
votes
1answer
76 views

Another LU decomposition?

I was asked to find LU decomposition of the following matrix without using a permutation: $$A=\begin{bmatrix}1 & 2 & 3 \\ 1 & 2 & 4\\ 1 & 2 & 5 \end{bmatrix}$$ I found one of ...
1
vote
1answer
25 views

positive definite how to prove that LU decomposition is possible

Given K a symmetrical, square and positive definite matrix, how to prove that LU decomposition is possible without the need of a permutation?
0
votes
1answer
38 views

Does this matrix has a single LU decomposition?

Let A be equal to this matrix: Does this matrix has a single LU decomposition? It is simple to find a decomposition without permutations. However how can I tell if there is more than one? ...
0
votes
2answers
47 views

The number of operations to multiply L by U?

I have the following $A=LU$ while $L$ is is lower triangular matrix and $U$ is an upper triangular matrix, the size of both $L$ and $U$ is $N\times N$. The question is how many operations are ...
0
votes
1answer
41 views

Row span in an LU Decomposition

It's easy to prove that if a $n \times n$ matrix $A$ has a unit LU decomposition $A=LU$, then the span of the rows of $A$ is the same as the span as the rows of $U$. Numerical experimentation seems to ...
0
votes
0answers
23 views

LU decomposition 2x2 matrix restrictions?

Wikipedia states that: If matrix A is invertible, then it admits an LU (or LDU) factorization if and only if all its leading principal minors are nonzero. However matrix \begin{bmatrix}0&1\\1&...
1
vote
1answer
60 views

LU factorization of a singular matrix

I am trying to find the LU factorisation of the following matrix: $$A=\begin{pmatrix} 1 & 0 & 3 \\ 2 & 2 & 2 \\ 3 & 6 & -3 \end{pmatrix}.$$ Note that $A$ is singular. I ...
1
vote
1answer
69 views

What is the best way to solve square integer matrices of 8-bit?

Assume that we want to solve this linear system: $$A^TA x = b$$ Matrix $A$ is square and random integer of 8-bit, e.g numbers between 0 and 255. Vector $b$ is known as well and also integer of 8-bit....
0
votes
2answers
217 views

Matrices: LDU Decomposition

Can someone please help me with the following: Let $L_1$ and $L_2$ be nonsingular lower triangular matrices and let $U_1$ and $U_2$ be nonsingular upper triangular matrices. If $L_1$$U_1$ = $L_2$$U_2$...
0
votes
1answer
32 views

Confused about a step in a LU decomposition with partial pivoting algorithm

Algorithm (LU Factorization with Partial Pivoting) Initialize $U = A, L = I, P = I $ FOR $k = 1 : m − 1$ $⠀ ⠀ ⠀ $Select $i ≥ k$ to maximize $|U(i,k)|$ $⠀ ⠀ ⠀ $$U ( k , k : m ) ←→ U ( i , k : ...
3
votes
3answers
153 views

Why is $LU$ preferred over $A^{-1}$ to solve matrix equations?

I understand the whole $LU$-decomposition vs Gaussian elimination argument. The fact that you can isolate the computationally expensive elimination step and re-use the $L$ and $U$ matrices for $Ax=b$ ...
0
votes
1answer
62 views

LU decomposition of invertible matrix

Let $M\in M(n\times n,\mathbb{R})$ such that $$M=\begin{pmatrix}a & c & 0 & \ldots & \ldots & 0 & d \\ e & a & c & \ddots & \ddots & \vdots & d \\ 0 &...
0
votes
1answer
44 views

LU Decomposition (added coulumn and row)

$$ \begin{array}{l}{\text { The regular Matrix } A \in \mathbb{R}^{n \times n} \text { with the LU decomposition } A=L R \text { gets an extra column }} \\ {\text { anr row so }} \\ {\qquad \widehat{A}...
1
vote
1answer
365 views

Gaussian LU and Crout's Method give me different answers

My book -Numerical Method- said, The Crout's method (LU Decomposition) formula is given by $$ \begin{aligned} A&= \begin{bmatrix} a_{11} & a_{12}& a_{13} \\ a_{21} & a_{22}& a_{...
0
votes
1answer
532 views

LU factorization for finding inverse matrix

I have the following matrix: $$ A|\underline{b} = \left ( \begin{array}{lll|l} -3 & 2 & 1 & -1 \\ 1 & 0 & -1 & -1 \\ 4 & -2 & 2 & -2 \end{array} \right ) $$ I ...
0
votes
1answer
298 views

Solutions of Matrix Equation $AXB^T = C$

Problem For given matrices $A$, $B$ and $C$, solve the equation $$AXB^T = C$$ for $X$ in terms of the LU decompositions of $A$ and $B$. When are there no solutions? Attempt at a Solution I know ...
2
votes
1answer
50 views

Cholesky solve for semi-definite system

I am thinking about the following linear algebra problem: $$ Ax = b $$ where $A$ is an $n$ by $n$ positive semi-definite matrix, in particular, it is rank $n-1$ with null space span$\{e=(1,1,\ldots,1)^...
1
vote
1answer
198 views

Solving powered matrix using LU decomposition

My task is to solve using $LU$ decomposition $A^k x = b$ where $k$ is a positive integer. I can raise the matrix $A$ to the power of $k$ and use $LU$ decomposition to solve the linear system $A^k x = ...
0
votes
0answers
19 views

Calculate the computation cost

Let $f(n)$ be the cost of computation of the LU analysis of a mtarix $A\in \mathbb{R}^{n\times n}$ and let $g(n)$ nbe the cost of the computation of the solution of a linear system, given the LU ...
4
votes
2answers
647 views

Condition number and $LU$ decomposition

Consider $A: n \times n$ non-singular and the factors $L$ and $U$ of $A$ obtained with partial pivoting strategy, such as: $PA = LU$. Proof that $$\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{\...
0
votes
1answer
588 views

How to solve $Ax=b$ wihout inverting $A$?

I'm going to solve this equation: $$Ax=b$$ Onto an embedded system with using C-programing language. It need to be fast as possible. Assume that $A$ is not square. One way to solve this is to use: $...