Mixing
Can't understand step in LU decomposition proof
$begingroup$
UPDATE: The author of the linked article has updated the proof and now it's perfectly clear.
I'm reading about the LU decomposition on this page and cannot understand one of the final steps in the proof to the following:
Let $A$ be a $Ktimes K$ matrix. Then, there exists a permutation matrix $P$ such that $PA$ has an LU decomposition: $$PA=LU$$ where $L$ is a lower triangular $Ktimes K$ matrix and $U$ is an upper triangular $Ktimes K$ matrix.
I'll reproduce the proof here:
Through Gaussian elimination, $A$ can be reduced to a row-echelon (hence upper triangular) matrix $U$ via a series of $n$ elementary operations: $$E_nbulletldotsbullet E_1bullet A = U$$
Any elementary matrix $E_i$ used in Gaussian elimination is either a permutation matrix $P_i$ or a matrix $L_i$ used to add a multiple of one row to a row below it. Thus, $L_i$ will be lower triangular with non-zero diagonal $implies$ invertible. Suppose that the first permutation matrix we encounter is in position $j$, so that we have:
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bulletldotsbullet L_1bullet A = U$$
Since a permutation matrix is orthogonal, $P_j^T P_j = I$ and hence
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bullet P_j^TP_j bulletldotsbullet P_j^TP_jbullet L_1bullet P_j^TP_jbullet A = U$$ or
$$E_nbulletldotsbullet E_{j+1}bullettilde{L}_{j-1}bulletldotsbullettilde{L}_1bullet P_jbullet A = U$$
for $i=1,ldots,j-1$. A matrix $L_i$, used to add $alpha$ times the $i$-th row to the $s$-th row (in this case $s>i$), can be written as a rank one update to the identity matrix: $L_i=I+M$, where $M$ is a matrix whose entries are all zeros except $M_{si} = alpha$. We have that
$$tilde{L}_i = P_jL_iP_j^T = P_j(I+M)P_j^T = P_jP_j^T + P_jMP_j^T = I+P_jMP_j^T$$
So far so good. Then we have:
The permutations performed on the rows and columns of $M$ by $P_j$ and $P_j^T$ can move the only non-zero element of $M$, but that element remains below the main diagonal (because $j>i$).
I can't understand this. $M$ is derived from $L_i$, which means that $M_{si} = alpha neq 0$ and all other elements of $M$ are $0$. Nothing has been said about $P_j$. I'm guessing $P_j$ swaps $j$-th row with $r$-th row, where $r>j$. What do the indices $s,i$ have anything to do with the indices $r,j$?
Would be grateful if anyone could clear this up!
linear-algebra matrices
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
$endgroup$
add a comment |
$begingroup$
UPDATE: The author of the linked article has updated the proof and now it's perfectly clear.
I'm reading about the LU decomposition on this page and cannot understand one of the final steps in the proof to the following:
Let $A$ be a $Ktimes K$ matrix. Then, there exists a permutation matrix $P$ such that $PA$ has an LU decomposition: $$PA=LU$$ where $L$ is a lower triangular $Ktimes K$ matrix and $U$ is an upper triangular $Ktimes K$ matrix.
I'll reproduce the proof here:
Through Gaussian elimination, $A$ can be reduced to a row-echelon (hence upper triangular) matrix $U$ via a series of $n$ elementary operations: $$E_nbulletldotsbullet E_1bullet A = U$$
Any elementary matrix $E_i$ used in Gaussian elimination is either a permutation matrix $P_i$ or a matrix $L_i$ used to add a multiple of one row to a row below it. Thus, $L_i$ will be lower triangular with non-zero diagonal $implies$ invertible. Suppose that the first permutation matrix we encounter is in position $j$, so that we have:
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bulletldotsbullet L_1bullet A = U$$
Since a permutation matrix is orthogonal, $P_j^T P_j = I$ and hence
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bullet P_j^TP_j bulletldotsbullet P_j^TP_jbullet L_1bullet P_j^TP_jbullet A = U$$ or
$$E_nbulletldotsbullet E_{j+1}bullettilde{L}_{j-1}bulletldotsbullettilde{L}_1bullet P_jbullet A = U$$
for $i=1,ldots,j-1$. A matrix $L_i$, used to add $alpha$ times the $i$-th row to the $s$-th row (in this case $s>i$), can be written as a rank one update to the identity matrix: $L_i=I+M$, where $M$ is a matrix whose entries are all zeros except $M_{si} = alpha$. We have that
$$tilde{L}_i = P_jL_iP_j^T = P_j(I+M)P_j^T = P_jP_j^T + P_jMP_j^T = I+P_jMP_j^T$$
So far so good. Then we have:
The permutations performed on the rows and columns of $M$ by $P_j$ and $P_j^T$ can move the only non-zero element of $M$, but that element remains below the main diagonal (because $j>i$).
I can't understand this. $M$ is derived from $L_i$, which means that $M_{si} = alpha neq 0$ and all other elements of $M$ are $0$. Nothing has been said about $P_j$. I'm guessing $P_j$ swaps $j$-th row with $r$-th row, where $r>j$. What do the indices $s,i$ have anything to do with the indices $r,j$?
Would be grateful if anyone could clear this up!
linear-algebra matrices
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
$endgroup$
add a comment |
$begingroup$
UPDATE: The author of the linked article has updated the proof and now it's perfectly clear.
I'm reading about the LU decomposition on this page and cannot understand one of the final steps in the proof to the following:
Let $A$ be a $Ktimes K$ matrix. Then, there exists a permutation matrix $P$ such that $PA$ has an LU decomposition: $$PA=LU$$ where $L$ is a lower triangular $Ktimes K$ matrix and $U$ is an upper triangular $Ktimes K$ matrix.
I'll reproduce the proof here:
Through Gaussian elimination, $A$ can be reduced to a row-echelon (hence upper triangular) matrix $U$ via a series of $n$ elementary operations: $$E_nbulletldotsbullet E_1bullet A = U$$
Any elementary matrix $E_i$ used in Gaussian elimination is either a permutation matrix $P_i$ or a matrix $L_i$ used to add a multiple of one row to a row below it. Thus, $L_i$ will be lower triangular with non-zero diagonal $implies$ invertible. Suppose that the first permutation matrix we encounter is in position $j$, so that we have:
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bulletldotsbullet L_1bullet A = U$$
Since a permutation matrix is orthogonal, $P_j^T P_j = I$ and hence
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bullet P_j^TP_j bulletldotsbullet P_j^TP_jbullet L_1bullet P_j^TP_jbullet A = U$$ or
$$E_nbulletldotsbullet E_{j+1}bullettilde{L}_{j-1}bulletldotsbullettilde{L}_1bullet P_jbullet A = U$$
for $i=1,ldots,j-1$. A matrix $L_i$, used to add $alpha$ times the $i$-th row to the $s$-th row (in this case $s>i$), can be written as a rank one update to the identity matrix: $L_i=I+M$, where $M$ is a matrix whose entries are all zeros except $M_{si} = alpha$. We have that
$$tilde{L}_i = P_jL_iP_j^T = P_j(I+M)P_j^T = P_jP_j^T + P_jMP_j^T = I+P_jMP_j^T$$
So far so good. Then we have:
The permutations performed on the rows and columns of $M$ by $P_j$ and $P_j^T$ can move the only non-zero element of $M$, but that element remains below the main diagonal (because $j>i$).
I can't understand this. $M$ is derived from $L_i$, which means that $M_{si} = alpha neq 0$ and all other elements of $M$ are $0$. Nothing has been said about $P_j$. I'm guessing $P_j$ swaps $j$-th row with $r$-th row, where $r>j$. What do the indices $s,i$ have anything to do with the indices $r,j$?
Would be grateful if anyone could clear this up!
linear-algebra matrices
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
$endgroup$
UPDATE: The author of the linked article has updated the proof and now it's perfectly clear.
I'm reading about the LU decomposition on this page and cannot understand one of the final steps in the proof to the following:
Let $A$ be a $Ktimes K$ matrix. Then, there exists a permutation matrix $P$ such that $PA$ has an LU decomposition: $$PA=LU$$ where $L$ is a lower triangular $Ktimes K$ matrix and $U$ is an upper triangular $Ktimes K$ matrix.
I'll reproduce the proof here:
Through Gaussian elimination, $A$ can be reduced to a row-echelon (hence upper triangular) matrix $U$ via a series of $n$ elementary operations: $$E_nbulletldotsbullet E_1bullet A = U$$
Any elementary matrix $E_i$ used in Gaussian elimination is either a permutation matrix $P_i$ or a matrix $L_i$ used to add a multiple of one row to a row below it. Thus, $L_i$ will be lower triangular with non-zero diagonal $implies$ invertible. Suppose that the first permutation matrix we encounter is in position $j$, so that we have:
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bulletldotsbullet L_1bullet A = U$$
Since a permutation matrix is orthogonal, $P_j^T P_j = I$ and hence
$$E_nbulletldotsbullet E_{j+1}bullet P_jbullet L_{j-1}bullet P_j^TP_j bulletldotsbullet P_j^TP_jbullet L_1bullet P_j^TP_jbullet A = U$$ or
$$E_nbulletldotsbullet E_{j+1}bullettilde{L}_{j-1}bulletldotsbullettilde{L}_1bullet P_jbullet A = U$$
for $i=1,ldots,j-1$. A matrix $L_i$, used to add $alpha$ times the $i$-th row to the $s$-th row (in this case $s>i$), can be written as a rank one update to the identity matrix: $L_i=I+M$, where $M$ is a matrix whose entries are all zeros except $M_{si} = alpha$. We have that
$$tilde{L}_i = P_jL_iP_j^T = P_j(I+M)P_j^T = P_jP_j^T + P_jMP_j^T = I+P_jMP_j^T$$
So far so good. Then we have:
The permutations performed on the rows and columns of $M$ by $P_j$ and $P_j^T$ can move the only non-zero element of $M$, but that element remains below the main diagonal (because $j>i$).
I can't understand this. $M$ is derived from $L_i$, which means that $M_{si} = alpha neq 0$ and all other elements of $M$ are $0$. Nothing has been said about $P_j$. I'm guessing $P_j$ swaps $j$-th row with $r$-th row, where $r>j$. What do the indices $s,i$ have anything to do with the indices $r,j$?
Would be grateful if anyone could clear this up!
linear-algebra matrices
linear-algebra matrices
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
edited Jan 31 at 21:23
Shirish Kulhari
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
asked Jan 30 at 18:12
Shirish KulhariShirish Kulhari
972217
972217
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your proof states $P_j$ is a permutation matrix. There is no explicit restriction on what $P_j$ permutes, but there is an implicit one, which has to do with the order in which row reduction steps are done.
Since $j > i$, meaning that $P_j$ was performed after the lower triangulars $L_1, L_2, ldots, L_{j-1}$, it must be the case that $P_j$ only permutes rows $j+1$ and greater (since rows 1 through $j$ are taken care of by the lower triangulars $L_1, L_2, ldots, L_{j-1}$). So, if $P_j$ swaps the rows $q$ and $r$, we have $q,r > j ge s > i$.
Basically, the implicit restriction on $P_j$ leaves $tilde L_i = L_i$, since the elements of $P_j$ and $P_j^T$ are the same as $I$ for rows/columns $1$ through $j$.
FWIW - the fact that this detail was not mentioned in my opinion makes this proof fairly poorly constructed, and introducing all of the $tilde L$ notation makes it difficult to parse. A much better proof approach would be to demonstrate that $L_i$ and $P_j$ commute.
Example. In this example, we will take
$i = 1$ (column number of nonzero element of $M$)
$s = 2$ (row number of nonzero element of $M$)
$j = 2$ (row reduction step number of permutation $P$)
$q = 3$ (one of two rows permuted by $P$)
$r = 4$ (one of two rows permuted by $P$)
A possible choice of $L_1$ and $P_2$ are as follows.
$$L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix} hspace{1 in} P_2 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
From these, we can derive $M$ and $P^T$.
$$M = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} hspace{1 in} P_2^T = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
Now, compute $tilde L_1 = P_2 MP_2^T$ and notice that it equals $L_1$, and is thus lower diagonal.
$$tilde L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix}begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
$$tilde L_1 = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} = L_1$$
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
$endgroup$
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093897%2fcant-understand-step-in-lu-decomposition-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your proof states $P_j$ is a permutation matrix. There is no explicit restriction on what $P_j$ permutes, but there is an implicit one, which has to do with the order in which row reduction steps are done.
Since $j > i$, meaning that $P_j$ was performed after the lower triangulars $L_1, L_2, ldots, L_{j-1}$, it must be the case that $P_j$ only permutes rows $j+1$ and greater (since rows 1 through $j$ are taken care of by the lower triangulars $L_1, L_2, ldots, L_{j-1}$). So, if $P_j$ swaps the rows $q$ and $r$, we have $q,r > j ge s > i$.
Basically, the implicit restriction on $P_j$ leaves $tilde L_i = L_i$, since the elements of $P_j$ and $P_j^T$ are the same as $I$ for rows/columns $1$ through $j$.
FWIW - the fact that this detail was not mentioned in my opinion makes this proof fairly poorly constructed, and introducing all of the $tilde L$ notation makes it difficult to parse. A much better proof approach would be to demonstrate that $L_i$ and $P_j$ commute.
Example. In this example, we will take
$i = 1$ (column number of nonzero element of $M$)
$s = 2$ (row number of nonzero element of $M$)
$j = 2$ (row reduction step number of permutation $P$)
$q = 3$ (one of two rows permuted by $P$)
$r = 4$ (one of two rows permuted by $P$)
A possible choice of $L_1$ and $P_2$ are as follows.
$$L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix} hspace{1 in} P_2 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
From these, we can derive $M$ and $P^T$.
$$M = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} hspace{1 in} P_2^T = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
Now, compute $tilde L_1 = P_2 MP_2^T$ and notice that it equals $L_1$, and is thus lower diagonal.
$$tilde L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix}begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
$$tilde L_1 = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} = L_1$$
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
$endgroup$
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
add a comment |
$begingroup$
Your proof states $P_j$ is a permutation matrix. There is no explicit restriction on what $P_j$ permutes, but there is an implicit one, which has to do with the order in which row reduction steps are done.
Since $j > i$, meaning that $P_j$ was performed after the lower triangulars $L_1, L_2, ldots, L_{j-1}$, it must be the case that $P_j$ only permutes rows $j+1$ and greater (since rows 1 through $j$ are taken care of by the lower triangulars $L_1, L_2, ldots, L_{j-1}$). So, if $P_j$ swaps the rows $q$ and $r$, we have $q,r > j ge s > i$.
Basically, the implicit restriction on $P_j$ leaves $tilde L_i = L_i$, since the elements of $P_j$ and $P_j^T$ are the same as $I$ for rows/columns $1$ through $j$.
FWIW - the fact that this detail was not mentioned in my opinion makes this proof fairly poorly constructed, and introducing all of the $tilde L$ notation makes it difficult to parse. A much better proof approach would be to demonstrate that $L_i$ and $P_j$ commute.
Example. In this example, we will take
$i = 1$ (column number of nonzero element of $M$)
$s = 2$ (row number of nonzero element of $M$)
$j = 2$ (row reduction step number of permutation $P$)
$q = 3$ (one of two rows permuted by $P$)
$r = 4$ (one of two rows permuted by $P$)
A possible choice of $L_1$ and $P_2$ are as follows.
$$L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix} hspace{1 in} P_2 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
From these, we can derive $M$ and $P^T$.
$$M = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} hspace{1 in} P_2^T = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
Now, compute $tilde L_1 = P_2 MP_2^T$ and notice that it equals $L_1$, and is thus lower diagonal.
$$tilde L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix}begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
$$tilde L_1 = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} = L_1$$
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
$endgroup$
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
add a comment |
$begingroup$
Your proof states $P_j$ is a permutation matrix. There is no explicit restriction on what $P_j$ permutes, but there is an implicit one, which has to do with the order in which row reduction steps are done.
Since $j > i$, meaning that $P_j$ was performed after the lower triangulars $L_1, L_2, ldots, L_{j-1}$, it must be the case that $P_j$ only permutes rows $j+1$ and greater (since rows 1 through $j$ are taken care of by the lower triangulars $L_1, L_2, ldots, L_{j-1}$). So, if $P_j$ swaps the rows $q$ and $r$, we have $q,r > j ge s > i$.
Basically, the implicit restriction on $P_j$ leaves $tilde L_i = L_i$, since the elements of $P_j$ and $P_j^T$ are the same as $I$ for rows/columns $1$ through $j$.
FWIW - the fact that this detail was not mentioned in my opinion makes this proof fairly poorly constructed, and introducing all of the $tilde L$ notation makes it difficult to parse. A much better proof approach would be to demonstrate that $L_i$ and $P_j$ commute.
Example. In this example, we will take
$i = 1$ (column number of nonzero element of $M$)
$s = 2$ (row number of nonzero element of $M$)
$j = 2$ (row reduction step number of permutation $P$)
$q = 3$ (one of two rows permuted by $P$)
$r = 4$ (one of two rows permuted by $P$)
A possible choice of $L_1$ and $P_2$ are as follows.
$$L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix} hspace{1 in} P_2 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
From these, we can derive $M$ and $P^T$.
$$M = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} hspace{1 in} P_2^T = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
Now, compute $tilde L_1 = P_2 MP_2^T$ and notice that it equals $L_1$, and is thus lower diagonal.
$$tilde L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix}begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
$$tilde L_1 = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} = L_1$$
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
$endgroup$
Your proof states $P_j$ is a permutation matrix. There is no explicit restriction on what $P_j$ permutes, but there is an implicit one, which has to do with the order in which row reduction steps are done.
Since $j > i$, meaning that $P_j$ was performed after the lower triangulars $L_1, L_2, ldots, L_{j-1}$, it must be the case that $P_j$ only permutes rows $j+1$ and greater (since rows 1 through $j$ are taken care of by the lower triangulars $L_1, L_2, ldots, L_{j-1}$). So, if $P_j$ swaps the rows $q$ and $r$, we have $q,r > j ge s > i$.
Basically, the implicit restriction on $P_j$ leaves $tilde L_i = L_i$, since the elements of $P_j$ and $P_j^T$ are the same as $I$ for rows/columns $1$ through $j$.
FWIW - the fact that this detail was not mentioned in my opinion makes this proof fairly poorly constructed, and introducing all of the $tilde L$ notation makes it difficult to parse. A much better proof approach would be to demonstrate that $L_i$ and $P_j$ commute.
Example. In this example, we will take
$i = 1$ (column number of nonzero element of $M$)
$s = 2$ (row number of nonzero element of $M$)
$j = 2$ (row reduction step number of permutation $P$)
$q = 3$ (one of two rows permuted by $P$)
$r = 4$ (one of two rows permuted by $P$)
A possible choice of $L_1$ and $P_2$ are as follows.
$$L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix} hspace{1 in} P_2 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
From these, we can derive $M$ and $P^T$.
$$M = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} hspace{1 in} P_2^T = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
Now, compute $tilde L_1 = P_2 MP_2^T$ and notice that it equals $L_1$, and is thus lower diagonal.
$$tilde L_1 = begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix}begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0end{bmatrix}$$
$$tilde L_1 = begin{bmatrix} 0 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 end{bmatrix} = L_1$$
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
answered Jan 30 at 20:33
Trevor KafkaTrevor Kafka
5309
5309
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
add a comment |
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
Just one small detail. Is it certain that $q$ and $r$ are both greater than $j$? I mean, it could mean that that $P_j$ exchanges the $j$-th row with the $r$-th row, where $r > j$. But even then, the non-zero element of $M$ would stay in the lower triangle. Thanks so much!
$endgroup$
– Shirish Kulhari
Jan 30 at 22:09
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
$begingroup$
You can always do row reduction into echelon form with $q,r>j$, yes. You don't have to, but you always can. This proof demonstrates that it's always possible to factor $PA$ into $LU$, so the fact that you can, even though not necessarily, do row reduction this way does not contradict the proof.
$endgroup$
– Trevor Kafka
Jan 31 at 3:48
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3093897%2fcant-understand-step-in-lu-decomposition-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
