Mixing
Simultaneous triangularization of matrices
$begingroup$
Let $mathcal{F}={A_1,A_2,ldots,A_r}$ be a triangulable commuting family of $ntimes n$ matrices (that is, each $A_i$ is triangulable and $A_iA_j=A_jA_i$ for every $i,j$). I know that $mathcal{F}$ can be simultaneous triangularization, but what is the algorithm of finding the invertible matrix $P$ such that $P^{-1}A_iP$ is triangular? As a working example consider the matrices
$$
A=
begin{pmatrix}
-3 & 2 & -4 \
-1 & 0 & -1\
2 & -2 & 3
end{pmatrix}qquad
B=
begin{pmatrix}
3 & -2 & 2 \
-1 & 2 & -1\
-2 & 2 & -1
end{pmatrix}qquad
C=
begin{pmatrix}
1 & 0 & 1 \
1 & 0 & 1\
0 & 0 & 0
end{pmatrix}
$$
Here $AB=BA$, $AC=CA$ and $BC=CB$. In addition, the characteristic polynomials of these matrices are
$$
f_A(x)=x(x-1)(x+1)\
f_B(x)=(x-2)(x-1)^2\
f_C(x)=x^2(x-1)
$$
so each one of them is triangulable. Thanks!
linear-algebra matrices
asked May 24 '17 at 7:09
boazboaz
2,338614
$endgroup$
add a comment |
$begingroup$
Let $mathcal{F}={A_1,A_2,ldots,A_r}$ be a triangulable commuting family of $ntimes n$ matrices (that is, each $A_i$ is triangulable and $A_iA_j=A_jA_i$ for every $i,j$). I know that $mathcal{F}$ can be simultaneous triangularization, but what is the algorithm of finding the invertible matrix $P$ such that $P^{-1}A_iP$ is triangular? As a working example consider the matrices
$$
A=
begin{pmatrix}
-3 & 2 & -4 \
-1 & 0 & -1\
2 & -2 & 3
end{pmatrix}qquad
B=
begin{pmatrix}
3 & -2 & 2 \
-1 & 2 & -1\
-2 & 2 & -1
end{pmatrix}qquad
C=
begin{pmatrix}
1 & 0 & 1 \
1 & 0 & 1\
0 & 0 & 0
end{pmatrix}
$$
Here $AB=BA$, $AC=CA$ and $BC=CB$. In addition, the characteristic polynomials of these matrices are
$$
f_A(x)=x(x-1)(x+1)\
f_B(x)=(x-2)(x-1)^2\
f_C(x)=x^2(x-1)
$$
so each one of them is triangulable. Thanks!
linear-algebra matrices
asked May 24 '17 at 7:09
boazboaz
2,338614
$endgroup$
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03
add a comment |
$begingroup$
Let $mathcal{F}={A_1,A_2,ldots,A_r}$ be a triangulable commuting family of $ntimes n$ matrices (that is, each $A_i$ is triangulable and $A_iA_j=A_jA_i$ for every $i,j$). I know that $mathcal{F}$ can be simultaneous triangularization, but what is the algorithm of finding the invertible matrix $P$ such that $P^{-1}A_iP$ is triangular? As a working example consider the matrices
$$
A=
begin{pmatrix}
-3 & 2 & -4 \
-1 & 0 & -1\
2 & -2 & 3
end{pmatrix}qquad
B=
begin{pmatrix}
3 & -2 & 2 \
-1 & 2 & -1\
-2 & 2 & -1
end{pmatrix}qquad
C=
begin{pmatrix}
1 & 0 & 1 \
1 & 0 & 1\
0 & 0 & 0
end{pmatrix}
$$
Here $AB=BA$, $AC=CA$ and $BC=CB$. In addition, the characteristic polynomials of these matrices are
$$
f_A(x)=x(x-1)(x+1)\
f_B(x)=(x-2)(x-1)^2\
f_C(x)=x^2(x-1)
$$
so each one of them is triangulable. Thanks!
linear-algebra matrices
asked May 24 '17 at 7:09
boazboaz
2,338614
$endgroup$
Let $mathcal{F}={A_1,A_2,ldots,A_r}$ be a triangulable commuting family of $ntimes n$ matrices (that is, each $A_i$ is triangulable and $A_iA_j=A_jA_i$ for every $i,j$). I know that $mathcal{F}$ can be simultaneous triangularization, but what is the algorithm of finding the invertible matrix $P$ such that $P^{-1}A_iP$ is triangular? As a working example consider the matrices
$$
A=
begin{pmatrix}
-3 & 2 & -4 \
-1 & 0 & -1\
2 & -2 & 3
end{pmatrix}qquad
B=
begin{pmatrix}
3 & -2 & 2 \
-1 & 2 & -1\
-2 & 2 & -1
end{pmatrix}qquad
C=
begin{pmatrix}
1 & 0 & 1 \
1 & 0 & 1\
0 & 0 & 0
end{pmatrix}
$$
Here $AB=BA$, $AC=CA$ and $BC=CB$. In addition, the characteristic polynomials of these matrices are
$$
f_A(x)=x(x-1)(x+1)\
f_B(x)=(x-2)(x-1)^2\
f_C(x)=x^2(x-1)
$$
so each one of them is triangulable. Thanks!
linear-algebra matrices
linear-algebra matrices
asked May 24 '17 at 7:09
boazboaz
2,338614
asked May 24 '17 at 7:09
boazboaz
2,338614
edited May 24 '17 at 7:33
boaz
asked May 24 '17 at 7:09
boazboaz
2,338614
asked May 24 '17 at 7:09
boazboaz
2,338614
asked May 24 '17 at 7:09
boazboaz
2,338614
2,338614
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03
add a comment |
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here, it is easy. Since $A$ has $3$ distinct eigenvalues and $B,C$ commute with $A$, we can deduce that $B,C$ are polynomials in $A$ and it suffices to triangularize $A$.
In the general case.
Step 1. Find a common eigenvector of $A,B,C$.
Step 2. Proceed by recurrence.
Moreover, you can choose $P$ as an orthogonal matrix.
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
$endgroup$
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
add a comment |
$begingroup$
More explicitly: find a common eigenvector v1 among your given matrices. Now complete a basis arbitrarily *u2,...,un. Let Q = [v,u1,...,un ] a matrix. Now Q-1AQ, Q-1BQ, and Q-1CQ should all have an (n-1) x (n-1) submatrix in the bottom right with only zeros in the entries of first column directly to the left of it. You then want to find a common eigenvector w among all of these submatrices. Let U =[u1,...,un]. Then v2 =Uw. With this update *Q = [v1,v2,u3,...,un ] * where u3,...,un may have been rechosen in order to complete the space. You rinse and repeat with n-2, n-3 and so on.
If you need more information check out the algorithm in the paper by Dubi:
edited Jan 9 at 0:08
dantopa
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
$endgroup$
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%2f2294563%2fsimultaneous-triangularization-of-matrices%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here, it is easy. Since $A$ has $3$ distinct eigenvalues and $B,C$ commute with $A$, we can deduce that $B,C$ are polynomials in $A$ and it suffices to triangularize $A$.
In the general case.
Step 1. Find a common eigenvector of $A,B,C$.
Step 2. Proceed by recurrence.
Moreover, you can choose $P$ as an orthogonal matrix.
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
$endgroup$
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
add a comment |
$begingroup$
Here, it is easy. Since $A$ has $3$ distinct eigenvalues and $B,C$ commute with $A$, we can deduce that $B,C$ are polynomials in $A$ and it suffices to triangularize $A$.
In the general case.
Step 1. Find a common eigenvector of $A,B,C$.
Step 2. Proceed by recurrence.
Moreover, you can choose $P$ as an orthogonal matrix.
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
$endgroup$
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
add a comment |
$begingroup$
Here, it is easy. Since $A$ has $3$ distinct eigenvalues and $B,C$ commute with $A$, we can deduce that $B,C$ are polynomials in $A$ and it suffices to triangularize $A$.
In the general case.
Step 1. Find a common eigenvector of $A,B,C$.
Step 2. Proceed by recurrence.
Moreover, you can choose $P$ as an orthogonal matrix.
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
$endgroup$
Here, it is easy. Since $A$ has $3$ distinct eigenvalues and $B,C$ commute with $A$, we can deduce that $B,C$ are polynomials in $A$ and it suffices to triangularize $A$.
In the general case.
Step 1. Find a common eigenvector of $A,B,C$.
Step 2. Proceed by recurrence.
Moreover, you can choose $P$ as an orthogonal matrix.
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
answered May 24 '17 at 8:59
loup blancloup blanc
23.1k21850
23.1k21850
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
add a comment |
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Thanks @loup blanc. Two questions: (1) Does the matrices $A_i$ must have a common eigenvectors? (2) What do you mean by "Proceed by recurrence"?
$endgroup$
– boaz
May 24 '17 at 9:08
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Yes, they do have a common eigenvector $u$. Consider a basis in the form $u,cdots$ and use the same reasoning about the "right-lower" blocks of the new matrices.
$endgroup$
– loup blanc
May 24 '17 at 9:16
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
$begingroup$
Thanks @loup blanc for you answer.
$endgroup$
– boaz
May 24 '17 at 9:32
add a comment |
$begingroup$
More explicitly: find a common eigenvector v1 among your given matrices. Now complete a basis arbitrarily *u2,...,un. Let Q = [v,u1,...,un ] a matrix. Now Q-1AQ, Q-1BQ, and Q-1CQ should all have an (n-1) x (n-1) submatrix in the bottom right with only zeros in the entries of first column directly to the left of it. You then want to find a common eigenvector w among all of these submatrices. Let U =[u1,...,un]. Then v2 =Uw. With this update *Q = [v1,v2,u3,...,un ] * where u3,...,un may have been rechosen in order to complete the space. You rinse and repeat with n-2, n-3 and so on.
If you need more information check out the algorithm in the paper by Dubi:
edited Jan 9 at 0:08
dantopa
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
$endgroup$
add a comment |
$begingroup$
More explicitly: find a common eigenvector v1 among your given matrices. Now complete a basis arbitrarily *u2,...,un. Let Q = [v,u1,...,un ] a matrix. Now Q-1AQ, Q-1BQ, and Q-1CQ should all have an (n-1) x (n-1) submatrix in the bottom right with only zeros in the entries of first column directly to the left of it. You then want to find a common eigenvector w among all of these submatrices. Let U =[u1,...,un]. Then v2 =Uw. With this update *Q = [v1,v2,u3,...,un ] * where u3,...,un may have been rechosen in order to complete the space. You rinse and repeat with n-2, n-3 and so on.
If you need more information check out the algorithm in the paper by Dubi:
edited Jan 9 at 0:08
dantopa
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
$endgroup$
add a comment |
$begingroup$
More explicitly: find a common eigenvector v1 among your given matrices. Now complete a basis arbitrarily *u2,...,un. Let Q = [v,u1,...,un ] a matrix. Now Q-1AQ, Q-1BQ, and Q-1CQ should all have an (n-1) x (n-1) submatrix in the bottom right with only zeros in the entries of first column directly to the left of it. You then want to find a common eigenvector w among all of these submatrices. Let U =[u1,...,un]. Then v2 =Uw. With this update *Q = [v1,v2,u3,...,un ] * where u3,...,un may have been rechosen in order to complete the space. You rinse and repeat with n-2, n-3 and so on.
If you need more information check out the algorithm in the paper by Dubi:
edited Jan 9 at 0:08
dantopa
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
$endgroup$
More explicitly: find a common eigenvector v1 among your given matrices. Now complete a basis arbitrarily *u2,...,un. Let Q = [v,u1,...,un ] a matrix. Now Q-1AQ, Q-1BQ, and Q-1CQ should all have an (n-1) x (n-1) submatrix in the bottom right with only zeros in the entries of first column directly to the left of it. You then want to find a common eigenvector w among all of these submatrices. Let U =[u1,...,un]. Then v2 =Uw. With this update *Q = [v1,v2,u3,...,un ] * where u3,...,un may have been rechosen in order to complete the space. You rinse and repeat with n-2, n-3 and so on.
If you need more information check out the algorithm in the paper by Dubi:
edited Jan 9 at 0:08
dantopa
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
edited Jan 9 at 0:08
dantopa
6,46942243
edited Jan 9 at 0:08
dantopa
6,46942243
edited Jan 9 at 0:08
dantopa
6,46942243
6,46942243
answered Jan 8 at 21:57
JaMcJaMc
112
answered Jan 8 at 21:57
JaMcJaMc
112
answered Jan 8 at 21:57
JaMcJaMc
112
112
add a comment |
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%2f2294563%2fsimultaneous-triangularization-of-matrices%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
$begingroup$
The characteristic polynomial for $A$ seems wrong.
$endgroup$
– Emilio Novati
May 24 '17 at 7:32
$begingroup$
A typo..I fixed that ($-4$ in the 13 position). Thanks @Emilio Novati.
$endgroup$
– boaz
May 24 '17 at 7:34
$begingroup$
Do you know how to find the matrix $P$ for a single triangularizable matrix $A$?
$endgroup$
– Greg Martin
May 24 '17 at 8:22
$begingroup$
yes, i know how to do the trianglazation process with a single matrix.
$endgroup$
– boaz
May 24 '17 at 9:03