Questions tagged [lu-decomposition]
Questions regarding the numerical method LU decomposition to decompose a matrix into the multiplication of two triangular matrices: A lower triangle matrix and an upper triangular matrix
150
questions
0
votes
0
answers
19
views
Banded Matrix LU Decomposition
I have an $n$ by $n$ $k$-banded matrix for which I calculated the LU decomposition via Matlab.
Now, I want to solve the system to find the resulting vector and compare the operation count with another ...
0
votes
1
answer
55
views
Is the LU decomposition just Gauss-Jordan elimination?
I am watching Gilbert Strang's neat lecture on the LU decomposition, which is taught just after Gaussian elimination. $LU$ for a matrix $A$ was found doing $EA=U$ and finally $A=E^{-1}U$.
Seems to me, ...
- 111
1
vote
0
answers
42
views
Missing the point of LU factorization / decomposition
Gaussian Elimination
The system of linear equations $Ax = b$ may be solved by using Gaussian Elimination (GE) arriving to a Row Echelon Form R of the augmented matrix $[A b]$, and then using back-...
- 111
0
votes
0
answers
47
views
LU decomposition of a specific Vandermonde matrix
I was playing with some unrelated topic and randomly stumbled into following:
Suppose we have a $4 \times 4$ Vandermonde matrix where $x_i = (0,1,2,3)$
$
V =
\begin{pmatrix}
1 & x_0 & x_0^2 &...
2
votes
1
answer
40
views
Solving linear system with product of two N by N matrices
I'm trying to find an efficient way to solve a system of equations given by $STx = b$ where $S, T$ are N by N matrices that have a given LU decomposition for each. I believe the most efficient ...
- 23
0
votes
0
answers
15
views
Constrained Hankel matrix decomposition
I want to decompose a square Hankel matrix $\bf {H}$, whose elements below the anti-diagonal are zeros. The decomposed factors should necessarily meet the following constraints:
$$\begin{equation} \bf ...
- 47
3
votes
0
answers
28
views
Prove that a given statement is equivalent to a matrix possessing an $LU$-factorization
An $LU$-factorization of a matrix $A$ is a way to write $A$ as the product of a lower triangular matrix $L$ and an upper triangular matrix $U$, where the lower triangular matrix has $1$'s on its ...
- 153
0
votes
1
answer
54
views
Uniqueness of the LUP decomposition
Given the matrix $$A=\begin{pmatrix} 0 & 0 & 2 \\ 1 & 2 & 3 \\ 2 & 2 & 3 \end{pmatrix},$$ I want to compute the LUP decomposition $PA=LU$.
Here's what I got:
$$P=\begin{pmatrix}...
- 2,388
0
votes
0
answers
28
views
LTU product of lower-triangular, tridiagonal and upper-triangular matrices
By direct computation, the product of lower-triangular, tridiagonal and upper-triangular square matrices of order $n$ is
$$
(\mathbf{LTU})_{i,j} = \sum_{k=1}^{\min(i,j)} l_{i,k} t_{k,k} u_{k,j} + \...
- 637
0
votes
1
answer
16
views
Can a matrix not admitting an LU decomposition be shifted so that it does admit an LU decomposition?
Almost all square matrices have an (unpivoted) LU decomposition, but some don't. The question I have is whether - assuming $M$ is a square matrix over $\mathbb R$ or $\mathbb C$ which does not admit ...
- 8,155
0
votes
1
answer
17
views
Does $M^2$ have an LU decomposition?
It's well known that matrices of the form $M^T M$ have an (unpivoted, of course) LU decomposition. In fact, because they are positive semidefinite, they have a Cholesky decomposition. The field here ...
- 8,155
1
vote
0
answers
54
views
Prove case for why LU Decomposition fails
I understand that for some square matrices, a LU decomposition (not talking about LUP) can fail to exist.
For example, the following matrix has no LU decomposition
$$
\begin{bmatrix}
0 & 1 \\ 2 &...
- 11
1
vote
0
answers
27
views
Find the volume of the box in $R^3$ that is spanned by the columns of $A$.
The full question is
Consider the matrix
$A=\begin{bmatrix}1&-1&1\\1&1&1\\1&-2&2\end{bmatrix}$.
(a). Find the $LU$ decomposition of $A$.
(b). Find the volume of the box in $R^...
- 135
0
votes
0
answers
84
views
QR decomposition with R having values with alternating signs on diagonal
Suppose a real-valued n × n matrix A has a QR decomposition A = QR, where Q
is an orthogonal matrix, and R is an upper triangular matrix.
Give a method that uses this
decomposition to construct ...
0
votes
0
answers
75
views
LU factorisation of a tridiagonal matrix using MATLAB
I am trying to create a function called function [l, d, u] = tridiag_factorlu(A). It takes as argument a general tridiagonal matrix A, which is stored as a normal ...
- 1
1
vote
0
answers
22
views
Decomposing a matrix that has duplicate columns using PA=LU factorization
I am given the following matrix.
$$ A = \begin{bmatrix} 3 & 3 & 9 & 6 \\ 4 & 4 &4 &4 \\ 1 & 1 & 5 & 5 \\ 2 & 2 & 4 & 6\end{bmatrix} $$
As you can notice,...
- 37
0
votes
0
answers
32
views
Ways of showing that the LU decomposition of a square matrix almost always exists?
We know that (in the measure-theoretic sense) almost all square matrices $M$ over $\mathbb R$ admit an LU decomposition: $M = LDU$. We are using the Lebesgue measure, and we may treat for each fixed $...
- 8,155
1
vote
0
answers
85
views
Norm of Lower Traingular matrix of a LU decomposition $\|L\|_{\infty}\le n $
In LU factorization of a square matrix , show that
$\|L\|_F \le \frac{n(n+1)}{2}$
$\|L\|_{\infty}\le n $
$\|L\|_1\le n$
$\|L\|_2 \le n$
Now here in $L$ all diagonal elements are $1$.Now Frobenius ...
- 99
1
vote
1
answer
51
views
Completing the square when the pivot are zeros.
I watched the 18.06 MIT course on linear Algebra online. It shows a nice method to complete the square using Gauss elimination.
For example if I consider the quadratic form \begin{equation}x^2+y^2+4xy=...
- 103
2
votes
0
answers
89
views
Do positive semidefinite matrix have LU decomposition? [closed]
Suppose we have a real matrix $A=R R^t$ where $R$ is triangular. Since there is no restriction on $R$ we can say that $A$ is positive semidefinite. Can I affirm that $A$ has LU decomposition (L lower ...
- 21
0
votes
0
answers
257
views
Matlab. LU decomposition Crout's Method. And usage of decomposition on accurate Block Matrix.
I have to implement such a program()Look at picture I attached
I mostly implemented everything: Crout's Algorithm, solving linear equations, I created this block matrix, but I don't know to use that ...
0
votes
0
answers
176
views
MATLAB Code Help. Using Crout's Method, solve the system of linear equation $Mz=f$, where $M=\begin{pmatrix}I &A\\A^T&0\end{pmatrix}$
Using Crout's Method, solve the system of linear equation $Mz=f$, where $$M=\begin{pmatrix}I &A\\A^T&0\end{pmatrix}$$
I have implemented algorithm of Crout's method. But I don't have any idea ...
2
votes
2
answers
89
views
What's the fastest way to solve a system of equations a million times such that the coefficient matrix is same but the constant matrix is different?
I need an efficient way to solve $Ax=C$ a million times such that coefficient matrix $A$ is always the same but the constant matrix $C$ is always different for each of the million problems.
To solve ...
0
votes
1
answer
119
views
Why $L^{-1}U^T=D$ in LU decomposition?
I learned that given a matrix $A$, we can apply LU decomposition to get $A=LU$, where $L$ is lower triangular and $U$ is upper triangular. Further, if $A$ is symmetric (or Hermitian for complex $A$), ...
- 103
0
votes
1
answer
327
views
Determine if LU decomposition is possible on a matrix?
I am trying to understand how you determine if LU decomposition is possible on a given matrix. I believe the way to calculate this is to check if the leading-matrices have non-zero determinants. I ...
- 147
0
votes
1
answer
119
views
Do the rows used in row operations during LU factorisation matter?
A method I have seen for finding the LU factorisation of a matrix is that U is the row echelon form of A. The row operations we perform on A to get to U must involve replacing $R_i$ by $R_i - kR_j$ ...
- 304
1
vote
1
answer
103
views
Solving System of linear equation using LU decomposition
I am working on a simultaneous linear equation problem using LU decomposition
and I'm unsure if this is the correct approach/answer to solve a system of simultaneous equations using LU decomposition. ...
- 147
1
vote
0
answers
34
views
Solving System of linear equation containing decimals
I am working on a simultaneous linear equation problem using LU decomposition.
$5x1 + 6x2 + 2.3x3 + 6x4 = 4$
$9x1 + 2x2 + 3.5x3 + 7x4 = 5$
$3.5x1 + 6x2 + 2x3 + 3x4 = 6.7$
$1.5x1 + 2x2 + 1.5x3 + 6x4 = ...
- 147
1
vote
0
answers
66
views
Is my LU Factorization Incorrect?
I have the following matrix I am trying to decompose into it's respective $L$ and $U$ parts for $A = LU$.
So I have $$\begin{bmatrix} 1 && 4 && 3 \\ 0 && -10 && -5 \\ 0 ...
- 99
0
votes
1
answer
95
views
generalization of LU decomposition?
I've just begun studying numerical approaches to LU decomposition and it got me thinking. Is there a more "general" (not sure if this is the right term for what I'm describing) form of LU ...
- 1
0
votes
1
answer
55
views
LU- decomposition
Find an LU-decomposition of the coefficient matrix and solve the system $$\begin{pmatrix}
1 & 4 & 3\\ -1 & -1 & 3 \\ 2 & 9 & 8 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \...
- 61
0
votes
0
answers
51
views
A question about the product of commutators in an article of Vaserstein
The question comes from Lemma 13. It is stated as follows.
Let $A$ be an associative ring with $1$, and $n\geq2$ an integer. Assume that either $n\geq3$ or $n=2$, and $1$ is the sum of two units in $...
- 687
0
votes
0
answers
24
views
Necessary and suffcient condition for LR-decompositions
Let $ A=\left(a_{i j}\right)_{i, j=1, \ldots, n} \in \mathbb{R}^{n \times n} $ be an invertible matrix.
Show that an $ L R $-decomposition of $ A $ exists if and only if $ \operatorname{det}\left(A^{[...
- 560
0
votes
0
answers
83
views
LU Decomposition without Gaussian Elimination
I'm creating a program to compute the LU factorization of a matrix, and I was wondering if there was a way to compute an LU factorization without using Gaussian Elimination.
I'm mainly worried about ...
- 53
1
vote
0
answers
53
views
Block LU factorization with more than two blocks?
If I have a symmetric, positive definite block matrix there exists the following LU decomposition:
$$\left[\matrix{A && B^\intercal \\ B && C}\right]=\left[\matrix{A^{\frac{1}{2}} &...
- 939
1
vote
0
answers
42
views
How to find a solution other than the vector $0$ of Linear System $AX=b$ with $b$ belonging to $0$
Hello I am currently trying to find the solution of a spring system without condition on border, so naturally my vector $b \in 0_{M\{n,1\}}$, I am resolving this system with an LU algorithm but ...
0
votes
1
answer
74
views
Do you have to start with the first row during LU decomposition?
I guess I've never run into this pretty simple problem, but I'm doing a Cholesky Factorization of the matrix shown below, and ran into some weird ambiguity in how I usually do $LU$ decomp:
$$ A = \...
2
votes
0
answers
189
views
Efficient LU decomposition of matrix after updating diagonal
I am computing LU decomposition of $(kD + A)$ where $D$ is diagonal matrix with {$d_{1}$, $d_{2}$, ... , $d_{n}$}, $A$ is a real symmetric positive-definite matrix, $k$ is a number that changes on ...
- 33
1
vote
1
answer
151
views
Is there any situation where the LDU decomposition is the same as the eigenvalue decomposition?
I was just wondering if there are any situation where the LDU decomposition is the same as eigenvalue decomposition (diagonalization)? The only way this can be possible if L and U are inverse so ...
- 4,229
1
vote
1
answer
108
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
0
answers
55
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$ ...
- 13.7k
2
votes
2
answers
153
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{...
- 13.7k
0
votes
1
answer
73
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 ...
1
vote
1
answer
54
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 ...
- 1,060
0
votes
1
answer
143
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 ...
- 11
0
votes
1
answer
263
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
...
- 414
1
vote
2
answers
386
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 ...
- 49
0
votes
1
answer
384
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 ...
- 1,368
0
votes
1
answer
335
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 ...
- 1,783
0
votes
1
answer
186
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 & ...
- 23