Given two similar matrices $A$, $B$, is there a way to find an invertible matrix $P$ such that $A=P^{-1}BP$?
up vote
3
down vote
favorite
I was wondering if given two similar square matrices $A$ and $B$ would always be possible to find an matrix $Pin GL(n)$ such that $A=P^{-1}BP$.
thank you!
linear-algebra matrices
asked Dec 10 '13 at 20:50
giulio
411413
add a comment |
up vote
3
down vote
favorite
I was wondering if given two similar square matrices $A$ and $B$ would always be possible to find an matrix $Pin GL(n)$ such that $A=P^{-1}BP$.
thank you!
linear-algebra matrices
asked Dec 10 '13 at 20:50
giulio
411413
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I was wondering if given two similar square matrices $A$ and $B$ would always be possible to find an matrix $Pin GL(n)$ such that $A=P^{-1}BP$.
thank you!
linear-algebra matrices
asked Dec 10 '13 at 20:50
giulio
411413
I was wondering if given two similar square matrices $A$ and $B$ would always be possible to find an matrix $Pin GL(n)$ such that $A=P^{-1}BP$.
thank you!
linear-algebra matrices
linear-algebra matrices
asked Dec 10 '13 at 20:50
giulio
411413
asked Dec 10 '13 at 20:50
giulio
411413
edited Dec 10 '13 at 21:00
asked Dec 10 '13 at 20:50
giulio
411413
asked Dec 10 '13 at 20:50
giulio
411413
asked Dec 10 '13 at 20:50
giulio
411413
411413
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51
add a comment |
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51
add a comment |
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}quad;quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
add a comment |
up vote
5
down vote
The short answer will be no. For example, let $Aneq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=Ineq A$ for all $Pin GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
--
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
add a comment |
up vote
2
down vote
Let $K$ be a subfield of $mathbb{C}$. We assume that $A,Bin M_n(K)$ are similar (that is, there is $Pin M_n(K)$ s.t. $det(P)not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $Pin E$ s.t. $det(P)not= 0$, ${Pin GL_n(K);PA=BP}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy.
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las Vegas algorithm can be used to compute both
the Frobenius form and a Frobenius transition matrix for a given $ntimes n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In "Algorithms for similarity transforms. In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$).
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless.
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
answered Nov 22 at 13:45
loup blanc
22.2k21749
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}quad;quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
add a comment |
up vote
3
down vote
accepted
Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}quad;quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}quad;quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
Let $J$ the Jordan canonical matrix similar to $A$ and $B$ so we can find the change basis matrices $Q$ and $S$ such that
$$A=QJQ^{-1}quad;quad B=SJS^{-1}$$
hence with $P=Q^{-1}S$ we have $A=P^{-1}BP$.
answered Dec 10 '13 at 21:00
user63181
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
add a comment |
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
Thank you for your answers. But what if we consider matrices over non algebrally closed fields?
– giulio
Dec 10 '13 at 21:27
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
$ddotsmile{}{}$
– mrs
Dec 11 '13 at 5:21
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
For me, I found an appropriate Q for A and an appropriate S for B. However, for $$A = P^{-1} B P$$ to be true, I had to use $$P = S Q^{-1}$$ instead.
– RAH
Nov 17 at 18:49
add a comment |
up vote
5
down vote
The short answer will be no. For example, let $Aneq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=Ineq A$ for all $Pin GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
--
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
add a comment |
up vote
5
down vote
The short answer will be no. For example, let $Aneq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=Ineq A$ for all $Pin GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
--
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
add a comment |
up vote
5
down vote
up vote
5
down vote
The short answer will be no. For example, let $Aneq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=Ineq A$ for all $Pin GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
--
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
The short answer will be no. For example, let $Aneq I$ and $B=I$. Then clearly $P^{-1}BP=P^{-1}IP=Ineq A$ for all $Pin GL_n(F)$.
You are looking for matrix similarity, and you can read about the conditions in the link above.
--
Edit: As the question was edited, now the answer is yes: For every matrix $A$ one can find its Jordan canonical form, $J_A$. Find the base change matrix $P_A$. Since $A$, $B$ are similar if and only if $J_A=J_B$, we have $J=P_AAP_A^{-1}=P_BBP_B^{-1}$. So $A=(P_B^{-1}P_A)^{-1}B(P_B^{-1}P_A)$
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
edited Dec 10 '13 at 21:05
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
answered Dec 10 '13 at 20:55
Dennis Gulko
13.9k12655
13.9k12655
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
add a comment |
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
sorry, I edited the text
– giulio
Dec 10 '13 at 21:00
add a comment |
up vote
2
down vote
Let $K$ be a subfield of $mathbb{C}$. We assume that $A,Bin M_n(K)$ are similar (that is, there is $Pin M_n(K)$ s.t. $det(P)not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $Pin E$ s.t. $det(P)not= 0$, ${Pin GL_n(K);PA=BP}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy.
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las Vegas algorithm can be used to compute both
the Frobenius form and a Frobenius transition matrix for a given $ntimes n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In "Algorithms for similarity transforms. In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$).
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless.
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
answered Nov 22 at 13:45
loup blanc
22.2k21749
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
add a comment |
up vote
2
down vote
Let $K$ be a subfield of $mathbb{C}$. We assume that $A,Bin M_n(K)$ are similar (that is, there is $Pin M_n(K)$ s.t. $det(P)not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $Pin E$ s.t. $det(P)not= 0$, ${Pin GL_n(K);PA=BP}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy.
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las Vegas algorithm can be used to compute both
the Frobenius form and a Frobenius transition matrix for a given $ntimes n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In "Algorithms for similarity transforms. In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$).
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless.
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
answered Nov 22 at 13:45
loup blanc
22.2k21749
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
add a comment |
up vote
2
down vote
up vote
2
down vote
Let $K$ be a subfield of $mathbb{C}$. We assume that $A,Bin M_n(K)$ are similar (that is, there is $Pin M_n(K)$ s.t. $det(P)not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $Pin E$ s.t. $det(P)not= 0$, ${Pin GL_n(K);PA=BP}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy.
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las Vegas algorithm can be used to compute both
the Frobenius form and a Frobenius transition matrix for a given $ntimes n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In "Algorithms for similarity transforms. In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$).
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless.
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
answered Nov 22 at 13:45
loup blanc
22.2k21749
Let $K$ be a subfield of $mathbb{C}$. We assume that $A,Bin M_n(K)$ are similar (that is, there is $Pin M_n(K)$ s.t. $det(P)not= 0$ and $PA=BP$). Note that we can always choose $P$ in $M_n(K)$.
Of course, it is important not to calculate Jordan's forms of $A,B$.
METHOD 1.
i) Solve the linear system $PA=BP$; the set of solutions $E$ is a sub-vector space of $M_n(K)$ of dimension $k=dim(C(A))geq n$. Note that, using the tensor product, there are methods that permit to solve such a system with complexity in $O(n^3)$ (and not in $O(n^6)$).
Since there is $Pin E$ s.t. $det(P)not= 0$, ${Pin GL_n(K);PA=BP}$ is Zariski open dense in $E$.
ii) Thus, it suffices to randomly choose the $k$ parameters that define an element of $E$ to obtain a required solution with probability $1$.
METHOD 2.
We can also use the Frobenius form over $K$. Indeed, $A,B$ have same Frobenius form $F$:
$A=QFQ^{-1},B=RFR^{-1}$ and the sequel is easy.
EDIT. Here is a quick history of the progress made in calculating the Frobenius form.
i) in "Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24:948–969, 1995"
M. Giesbrech gives a randomized method: a Las Vegas algorithm can be used to compute both
the Frobenius form and a Frobenius transition matrix for a given $ntimes n$ matrix over a field $F$ using an expected number of operations over $F$ that is in $O(n^3)$, with standard matrix and polynomial arithmetic, whenever $F$ has at least $n^2$ elements (to ensure a probability of success at least
$1/2$), and using an expected number of
operations in $O(n^3log_q(n))$ if $F$ is a finite field with size $q$.
ii) Storjohann [1997] exposed a deterministic method whose complexity is $O(n^3)$. cf.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2505
However, the previous method does not give, at the same time, the matrix of change of basis.
iii) In "Algorithms for similarity transforms. In
Seventh Rhine Work-shop on Computer Algebra
, Bregenz, Austria, March 2000"
A. Storjohann and G. Villard obtain (with the same complexity), at the same time, the Frobenius form $F$ and the transform matrix $V$ .
There is a gap. None of the previous methods allow to use the fast multiplication of Strassen (in $O(n^{2.81})$).
iv) W. Eberly, in "Asymptotically efficient algorithms for the
Frobenius form. Technical report, Department of
Computer Science, University of Calgary, 2000"
gives $F,V$ thanks to a Las Vegas algorithm (using Strassen) that has complexity $O(n^{2.81}log(n))$.
Note that, unlike an urban legend, the methods of Coppersmith-Winograd and of Le Gall are practically useless.
v) In 2007, C. Pernet and A. Storjohann, in "Faster Algorithms for the Characteristic Polynomial. ISSAC"
give $F$ (but not $V$) with a Las Vegas algorithm in $O(n^{2.81})$.
This is the state of play in 2011-2013. I don't know if an algorithm giving $F, V$ in $O(n^{2.81})$ was found in recent years.
answered Nov 22 at 13:45
loup blanc
22.2k21749
edited Nov 27 at 17:05
answered Nov 22 at 13:45
loup blanc
22.2k21749
answered Nov 22 at 13:45
loup blanc
22.2k21749
answered Nov 22 at 13:45
loup blanc
22.2k21749
22.2k21749
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
add a comment |
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
I wonder if there are improvements in $O(n^3)$ since 1997, and the open questions they put in their paper?
– i707107
Nov 23 at 23:07
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
@i707107 , read my edit.
– loup blanc
Nov 27 at 17:05
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f601836%2fgiven-two-similar-matrices-a-b-is-there-a-way-to-find-an-invertible-matrix%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
The definition of similarity between $A$ and $B$ is that there exists invertible $P$ such that $A = P^{-1}BP$.
– EuYu
Dec 10 '13 at 21:02
According to the definition of similarity one can say the following: When someone sells you two matrices $A$ and $B$, claiming that they are similar, he has to provide a $P$ with $A=P^{-1}B P$ to testify for this similarity.
– Christian Blatter
Dec 10 '13 at 21:02
There are a lot of "quantities" that are preserved by conjugation, for example if $A$ and $B$ have different ranks, determinants, sets of eigenvalues, and so on, then $A$ and $B$ can't be similar, meaning that no such $P$ exists in those cases.
– Jeppe Stig Nielsen
Dec 10 '13 at 21:02
I assume that $A$ and $B$ are similar and want to find $P$ that makes them similar
– giulio
Dec 10 '13 at 21:07
Through Smith normal form of the matrices, we are able to write an explicit algorithm producing such matrix $P$. This does not require the field to be algebraically closed.
– i707107
Nov 22 at 2:51