ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 16 Mar 2019 04:11:56 -0500transformation matrix for variable matrix of given jordan typehttp://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/
I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.
How do I tell sage my input has a given Jordan type?
My idea is to compute `A.jordan_form(transformation=True)` in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.
I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.Fri, 01 Mar 2019 12:12:49 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/Comment by rburing for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45736#post-id-45736The quotient ring is not so nice because it has zero divisors, but see my answer below.Sat, 09 Mar 2019 05:24:34 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45736#post-id-45736Comment by anne for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45715#post-id-45715Yes, it might. How do I do it, exactly?
I would work in the ring $R/I$, where $R$ is the polynomial ring generated by matrix coefficients, and $I$ is the ideal of the Jordan form. For instance, if I have a 5 by 5 matrix $A$ of type $(3,2)$ then
- rank A = 3 would be encoded by adding all 4 by 4 minors of A to I
- rank A^2 = 1 would be encoded by adding all 2 by 2 minors of A^2 to I
- and finally rank A^3 = 0 would be encoded by adding coefficients of A^3 to IThu, 07 Mar 2019 16:50:46 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45715#post-id-45715Comment by rburing for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45612#post-id-45612An alternative approach is to write $A = g^{-1}Jg$ with $g$ symbolic, and solve for $g$ such that $A$ is strictly upper triangular ($n(n+1)/2$ polynomial equations for the $n^2$ entries of $g$). Would that suffice, or not? What quotient ring did you want to work in?Sun, 03 Mar 2019 03:37:38 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45612#post-id-45612Comment by anne for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45604#post-id-45604In general, the constraints may be more complicated than setting some entries to zero. Either way, I want Sage to figure out those constraints for me, and solve something like $g A g^{-1} = J$ for a $g$, given variable $A$ and fixed $J$.
If I try `A.jordan_form()` in a quotient ring, I get a `NotImplementedError` :(Sat, 02 Mar 2019 13:55:01 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45604#post-id-45604Comment by anne for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45603#post-id-45603Sure. Say I have an arbitrary uppertriangular matrix of Jordan type $(2,1)$.
$$
A = \begin{pmatrix}
0 & A_{0} & A_{1} \\\
0 & 0 & A_{2} \\\
0 & 0 & 0
\end{pmatrix}
$$
By default `J_d, T_d = A.jordan_form(transformation=True)` gives
$$
J_d = \begin{pmatrix}
0 & 1 & 0 \\\
0 & 0 & 1 \\\
0 & 0 & 0
\end{pmatrix} \qquad T_d = \begin{pmatrix}A_{0} A_{2} & A_{1} & 0 \\\
0 & A_{2} & 0 \\\
0 & 0 & 1\end{pmatrix}
$$
However, I expect $$J = \begin{pmatrix}0 & 1 & 0 \\\
0 & 0 & 0 \\\
0 & 0 & 0\end{pmatrix}$$
In this case, I know that $A_2$ must be zero for $A$ to have Jordan type $(2,1)$ so I let $A' = A\big|_{A_2 = 0}$ and do `J, T = A'.jordan_form(transformation=True)` getting the desired
$$T = \begin{pmatrix}A_{0} & 0 & 0 \\\
0 & 1 & 1 \\\
0 & 0 & -\frac{A_{0}}{A_{1}}\end{pmatrix}$$Sat, 02 Mar 2019 13:15:56 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45603#post-id-45603Comment by rburing for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45601#post-id-45601Can you give a more explicit example?Sat, 02 Mar 2019 07:01:08 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45601#post-id-45601Answer by rburing for <p>related: question/10488/why-does-jordan_form-not-work-over-inexact-rings/</p>
<p>I have, say, a nilpotent uppertriangular matrix $A$, with variable entries, and of a given Jordan type, $J$ (block type $\lambda$). I would like to know the transformation matrix $g$ such that $g A g^{-1} = J$.</p>
<p>How do I tell sage my input has a given Jordan type?</p>
<p>My idea is to compute <code>A.jordan_form(transformation=True)</code> in the quotient ring of the variable entries, given $\lambda$. This requires my figuring out the relations imposed by the given Jordan type, itself not an easy task.</p>
<p>I would like to know if what I want is already implemented somewhere in Sage, or if there is a better way to implement it than what I propose.</p>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?answer=45735#post-id-45735We can set up the problem as follows:
n = 3
jordan_type = (2,1)
assert sum(jordan_type) == n
import itertools
A_coeff_names = {(i,j) : 'a_{}_{}'.format(i,j) for (i,j) in itertools.combinations(range(n),2)}
R = PolynomialRing(QQ, names=A_coeff_names.values())
A_coeff = {idx : R(A_coeff_names[idx]) for idx in A_coeff_names}
A = Matrix(R, n, A_coeff)
J = block_diagonal_matrix([jordan_block(0, s) for s in jordan_type], subdivide=False)
A necessary condition for $gAg^{-1} = J$ is that the rank of $A^k$ equals the rank of $J^k$ for $1 \leq k < n$.
(And since $A$ has all zeros as eigenvalues, this will give the right Jordan type.)
In particular it is necessary that the $(\operatorname{rank}(J^k)+1)$-minors of $A^k$ vanish; these are polynomial equations upon the coefficients of $A$:
A_coeff_eqns = []
J_power = identity_matrix(QQ, n)
A_power = identity_matrix(R, n)
for k in range(n):
r = J_power.rank()
# need (r+1) x (r+1) minors to vanish
A_coeff_eqns.extend([eqn for eqn in A_power.minors(r+1) if eqn != 0])
J_power *= J
A_power *= A
We can solve these equations symbolically, substitute a solution into $A$, change to an exact ring (the fraction field of the polynomial ring in the new variables), calculate the Jordan form (to be sure), and change the names of the variables back to the originals where possible:
A_coeff_symb = map(SR, A_coeff_names.values())
A_coeff_eqns_symb = map(SR, A_coeff_eqns)
for sol in solve(A_coeff_eqns_symb, A_coeff_symb):
# substitute symbolic solution
A_new = A.change_ring(SR).apply_map(lambda x: x.subs(sol))
A_new_vars = list(set(sum([list(x.variables()) for x in A_new.list()], [])))
# change ring to fraction field of polynomial ring in the new variables
A_new_ring = PolynomialRing(QQ, names=A_new_vars).fraction_field()
A_new_rat = A_new.change_ring(A_new_ring)
if A_new_rat.jordan_form(subdivide=False) != J:
continue
# change names of variables back to the originals where possible
A_final_subs = {A_new_rat[i,j] : A_coeff[(i,j)] for (i,j) in A_coeff if A_new_rat[i,j] in A_new_vars}
A_final = A_new_rat.apply_map(lambda x: x.subs(A_final_subs))
print A_final
print
print A_final.jordan_form(subdivide=False, transformation=True)[1]
print
print '---'
print
Output:
[ 0 a_0_1 a_0_2]
[ 0 0 0]
[ 0 0 0]
[ a_0_1 0 0]
[ 0 1 1]
[ 0 0 a_0_1/(-a_0_2)]
---
[ 0 0 a_0_2]
[ 0 0 a_1_2]
[ 0 0 0]
[a_0_2 0 1]
[a_1_2 0 0]
[ 0 1 0]
---
Beware that this assumes Sage can solve the polynomial equations symbolically, which may not be true for large `n`. To give Sage an easier time (though the solutions may become less pretty), you can replace the list of equations by a Groebner basis for the same ideal:
A_coeff_eqns = R.ideal(A_coeff_eqns).groebner_basis()Sat, 09 Mar 2019 05:19:51 -0600http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?answer=45735#post-id-45735Comment by rburing for <p>We can set up the problem as follows:</p>
<pre><code>n = 3
jordan_type = (2,1)
assert sum(jordan_type) == n
import itertools
A_coeff_names = {(i,j) : 'a_{}_{}'.format(i,j) for (i,j) in itertools.combinations(range(n),2)}
R = PolynomialRing(QQ, names=A_coeff_names.values())
A_coeff = {idx : R(A_coeff_names[idx]) for idx in A_coeff_names}
A = Matrix(R, n, A_coeff)
J = block_diagonal_matrix([jordan_block(0, s) for s in jordan_type], subdivide=False)
</code></pre>
<p>A necessary condition for $gAg^{-1} = J$ is that the rank of $A^k$ equals the rank of $J^k$ for $1 \leq k < n$.</p>
<p>(And since $A$ has all zeros as eigenvalues, this will give the right Jordan type.)</p>
<p>In particular it is necessary that the $(\operatorname{rank}(J^k)+1)$-minors of $A^k$ vanish; these are polynomial equations upon the coefficients of $A$:</p>
<pre><code>A_coeff_eqns = []
J_power = identity_matrix(QQ, n)
A_power = identity_matrix(R, n)
for k in range(n):
r = J_power.rank()
# need (r+1) x (r+1) minors to vanish
A_coeff_eqns.extend([eqn for eqn in A_power.minors(r+1) if eqn != 0])
J_power *= J
A_power *= A
</code></pre>
<p>We can solve these equations symbolically, substitute a solution into $A$, change to an exact ring (the fraction field of the polynomial ring in the new variables), calculate the Jordan form (to be sure), and change the names of the variables back to the originals where possible:</p>
<pre><code>A_coeff_symb = map(SR, A_coeff_names.values())
A_coeff_eqns_symb = map(SR, A_coeff_eqns)
for sol in solve(A_coeff_eqns_symb, A_coeff_symb):
# substitute symbolic solution
A_new = A.change_ring(SR).apply_map(lambda x: x.subs(sol))
A_new_vars = list(set(sum([list(x.variables()) for x in A_new.list()], [])))
# change ring to fraction field of polynomial ring in the new variables
A_new_ring = PolynomialRing(QQ, names=A_new_vars).fraction_field()
A_new_rat = A_new.change_ring(A_new_ring)
if A_new_rat.jordan_form(subdivide=False) != J:
continue
# change names of variables back to the originals where possible
A_final_subs = {A_new_rat[i,j] : A_coeff[(i,j)] for (i,j) in A_coeff if A_new_rat[i,j] in A_new_vars}
A_final = A_new_rat.apply_map(lambda x: x.subs(A_final_subs))
print A_final
print
print A_final.jordan_form(subdivide=False, transformation=True)[1]
print
print '---'
print
</code></pre>
<p>Output:</p>
<pre><code>[ 0 a_0_1 a_0_2]
[ 0 0 0]
[ 0 0 0]
[ a_0_1 0 0]
[ 0 1 1]
[ 0 0 a_0_1/(-a_0_2)]
---
[ 0 0 a_0_2]
[ 0 0 a_1_2]
[ 0 0 0]
[a_0_2 0 1]
[a_1_2 0 0]
[ 0 1 0]
---
</code></pre>
<p>Beware that this assumes Sage can solve the polynomial equations symbolically, which may not be true for large <code>n</code>. To give Sage an easier time (though the solutions may become less pretty), you can replace the list of equations by a Groebner basis for the same ideal:</p>
<pre><code>A_coeff_eqns = R.ideal(A_coeff_eqns).groebner_basis()
</code></pre>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45791#post-id-45791You're welcome! :)Sat, 16 Mar 2019 04:11:56 -0500http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45791#post-id-45791Comment by anne for <p>We can set up the problem as follows:</p>
<pre><code>n = 3
jordan_type = (2,1)
assert sum(jordan_type) == n
import itertools
A_coeff_names = {(i,j) : 'a_{}_{}'.format(i,j) for (i,j) in itertools.combinations(range(n),2)}
R = PolynomialRing(QQ, names=A_coeff_names.values())
A_coeff = {idx : R(A_coeff_names[idx]) for idx in A_coeff_names}
A = Matrix(R, n, A_coeff)
J = block_diagonal_matrix([jordan_block(0, s) for s in jordan_type], subdivide=False)
</code></pre>
<p>A necessary condition for $gAg^{-1} = J$ is that the rank of $A^k$ equals the rank of $J^k$ for $1 \leq k < n$.</p>
<p>(And since $A$ has all zeros as eigenvalues, this will give the right Jordan type.)</p>
<p>In particular it is necessary that the $(\operatorname{rank}(J^k)+1)$-minors of $A^k$ vanish; these are polynomial equations upon the coefficients of $A$:</p>
<pre><code>A_coeff_eqns = []
J_power = identity_matrix(QQ, n)
A_power = identity_matrix(R, n)
for k in range(n):
r = J_power.rank()
# need (r+1) x (r+1) minors to vanish
A_coeff_eqns.extend([eqn for eqn in A_power.minors(r+1) if eqn != 0])
J_power *= J
A_power *= A
</code></pre>
<p>We can solve these equations symbolically, substitute a solution into $A$, change to an exact ring (the fraction field of the polynomial ring in the new variables), calculate the Jordan form (to be sure), and change the names of the variables back to the originals where possible:</p>
<pre><code>A_coeff_symb = map(SR, A_coeff_names.values())
A_coeff_eqns_symb = map(SR, A_coeff_eqns)
for sol in solve(A_coeff_eqns_symb, A_coeff_symb):
# substitute symbolic solution
A_new = A.change_ring(SR).apply_map(lambda x: x.subs(sol))
A_new_vars = list(set(sum([list(x.variables()) for x in A_new.list()], [])))
# change ring to fraction field of polynomial ring in the new variables
A_new_ring = PolynomialRing(QQ, names=A_new_vars).fraction_field()
A_new_rat = A_new.change_ring(A_new_ring)
if A_new_rat.jordan_form(subdivide=False) != J:
continue
# change names of variables back to the originals where possible
A_final_subs = {A_new_rat[i,j] : A_coeff[(i,j)] for (i,j) in A_coeff if A_new_rat[i,j] in A_new_vars}
A_final = A_new_rat.apply_map(lambda x: x.subs(A_final_subs))
print A_final
print
print A_final.jordan_form(subdivide=False, transformation=True)[1]
print
print '---'
print
</code></pre>
<p>Output:</p>
<pre><code>[ 0 a_0_1 a_0_2]
[ 0 0 0]
[ 0 0 0]
[ a_0_1 0 0]
[ 0 1 1]
[ 0 0 a_0_1/(-a_0_2)]
---
[ 0 0 a_0_2]
[ 0 0 a_1_2]
[ 0 0 0]
[a_0_2 0 1]
[a_1_2 0 0]
[ 0 1 0]
---
</code></pre>
<p>Beware that this assumes Sage can solve the polynomial equations symbolically, which may not be true for large <code>n</code>. To give Sage an easier time (though the solutions may become less pretty), you can replace the list of equations by a Groebner basis for the same ideal:</p>
<pre><code>A_coeff_eqns = R.ideal(A_coeff_eqns).groebner_basis()
</code></pre>
http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45790#post-id-45790Thanks very much!Fri, 15 Mar 2019 23:19:25 -0500http://ask.sagemath.org/question/45593/transformation-matrix-for-variable-matrix-of-given-jordan-type/?comment=45790#post-id-45790