All Questions
Tagged with gaussian-elimination matrix-decomposition
29 questions
2
votes
1
answer
540
views
LU decomposition of banded matrix with partial pivoting
Disclaimer: I'm rusty as can be in this department.
I'm looking into how to implement a banded matrix LU decomposition with partial pivoting ($PA = LU$). So to start with I implemented regular matrix ...
- 123
0
votes
1
answer
242
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, ...
user1049492
1
vote
0
answers
56
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-...
user1049492
0
votes
1
answer
445
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$ ...
0
votes
0
answers
166
views
Row reducing an integer matrix
Given a $n\times n$ integer matrix, what is the best row reduction that can be found using only integer row operations of the form:
an integer multiple of row $i$ can be added to row $j$
row i can be ...
- 289
0
votes
1
answer
169
views
Integer row reduction without scalar multiplication
For which matrices is it possible to find the (unreduced, and with arbitrary pivot) Echelon form of a matrix following Gaussian elimination, but only with the row operations:
Adding/subtracting one ...
- 289
1
vote
0
answers
41
views
Conjecture with a three-diagonal system of equations
Everything in the sequel real-valued. And it is silently assumed that the denominators are non-zero, though the latter is not a trivial issue.
Consider a piece of an (infinitely) large system of ...
- 17.3k
1
vote
1
answer
296
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,593
4
votes
1
answer
136
views
Are elementary row operators in linear algebra mutually exclusive?
There are three types of elementary row operations: I) row switching, II) row multiplication and III) row addition, corresponding to three kinds of row operation matrix.
My question is that does ...
- 51
1
vote
3
answers
4k
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 ...
- 115
1
vote
1
answer
1k
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 ...
- 617
0
votes
1
answer
39
views
Matrix $E$ of the elimination
We have the matrix $$M=\begin{pmatrix}4 & 1 & 1 \\ 1 & 1 & 1 \\ 2 & 1 & -1\end{pmatrix}$$ I want to find the lower triangular matrix $E$ of the elimination.
Is this matrix $E$...
- 14.1k
1
vote
1
answer
996
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_{...
- 2,311
0
votes
1
answer
2k
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 ...
- 852
0
votes
0
answers
672
views
LU decomposition of matrix using column pivoting
I want to find the LU decomposition of the following matrix $A$ using Gauss algorithm and column pivoting. $$A=\begin{pmatrix}6 & 4 & 3 & 1\\ 1 & 1 & 0 & 2 \\ 2 & 3 & 1 ...
- 14.1k
1
vote
2
answers
1k
views
LU decomposition of SPD matrix without partial pivoting?
I get why diagonal dominant matrices do not need partial pivoting before Gaussian elimination can be applied in order to gain a LU decomposition, but why is this also the case for SPD matrices in ...
user571390
1
vote
3
answers
2k
views
Why does $L$ have to be lower triangular in the LU factorization?
I was studying LU factorization, when I didn't understand a particular phrase, or rather, how it works or why it works.
During LU factorization L is said to be a lower triangular matrix and U is ...
- 560
0
votes
1
answer
2k
views
Cost of LU decomposition (time cost)
After calculation of the cost of the steps of the LU decomposition, and we come to the end result:
$(2/3)n^3 - (2/3)n$ and we say the total cost is then $(2/3)n^3$ (ignoring the term $(-2/3)n$), ...
- 335
1
vote
0
answers
2k
views
Show $A$ has an $LU$ factorization if and only if for each $k$ with $ 1 \leq k \leq m$, the upper left block $A(1:k,1:k)$ is nonsingular.
Let $A$ be a nonsingular square matrix ($m \times m$). Show $A$ has an $LU$ factorization if and only if for each $k$ with $ 1 \leq k \leq m$, the upper left block $A(1:k,1:k)$ is nonsingular.
...
- 4,360
2
votes
1
answer
6k
views
Strictly column diagonally dominant matrices and Gaussian elimination with partial pivoting
Suppose $A \in \mathbb{C}^{m \times m}$ is strictly column diagonally dominant, which means that for each $k$,
$$\left| a_{kk} \right| > \sum_{j \neq k} \left|a_{jk}\right|$$
Show that if ...
- 1,335
16
votes
3
answers
6k
views
LU decomposition; do permutation matrices commute?
I have an assignment for my Numerical Methods class to write a function that finds the PA=LU
decomposition for a given matrix A and returns P, L, and U.
Nevermind the coding problems for a moment; ...
- 1,001
0
votes
0
answers
1k
views
numerical stability: LU decomposition
I'm trying to evaluate the numerical stability of LU decomposition.
I implemented code in java to calculate the inverse matrix with LU.
I made 3 attemps.
a) mantissa 4
b) mantissa 6
c) maschine ...
2
votes
1
answer
4k
views
Show that if the leading principal minors of a nonsingular $n\times n$ matrix $A$ are all nonzero then the matrix $A$ has $LU$ factorization
I am stucked at this problem:
Prove by induction that if the leading principal minors of an $n\times n$ nonsingular matrix $A$ are all nonzero then the matrix $A$ has $LU$ factorization.
(The $k$-...
- 2,517
3
votes
2
answers
2k
views
LU-factorization: why can't I get a unit lower triangular matrix?
I want to find an $LU$-factorization of the following matrix: \begin{align*} A = \begin{pmatrix} 3 & -6 & 9 \\ -2 & 7 & -2 \\ 0 & 1 & 5 \end{pmatrix} \end{align*} This matrix ...
- 5,239
15
votes
3
answers
34k
views
Time complexity of LU decomposition
I am trying to derive the LU decomposition time complexity for an $n \times n$ matrix.
Eliminating the first column will require $n$ additions and $n$ multiplications for $n-1$ rows. Therefore, the ...
- 525
0
votes
0
answers
120
views
Proving Frobenius Theorem for Eigen Values
In my mulitivariable calculus class to justify second derivative test my professor used a theorem he called the frobenius theorem. But when I searched on wiki all I could find was Perron Frobenius ...
- 6,208
6
votes
1
answer
5k
views
Is the U factor in LU decomposition for rectangular matrices always in row echelon form?
I have come across the following rectangular 5 x 10 matrix and carried out a LU decomposition of it, in the form PA = LU. The following matrices were obtained by function scipy.linalg.lu from module ...
- 221
4
votes
1
answer
3k
views
LU factorization problem - Writing a code, don't understand partial pivoting
I'm trying to write a matlab code for the following question:
The program gets a matrix $A$ (lets say square matrix) and it returns $P,L,U$ such that $PA=PLU$ and $P$ is the permutation matrix, the ...
- 12.9k
10
votes
2
answers
14k
views
Proof of uniqueness of LU factorization
The first question: what is the proof that LU factorization of matrix is unique? Or am I mistaken?
The second question is, how can theentries of L below the main diagonal be obtained from the matrix $...
- 101