Dror Bar-Natan: Classes: 2014-15: Math 1100 Algebra I:

Pensieve header: JCF tricks and programs - unified notebook.

JCF Tricks and Programs

Row and Column Operations

Row operations are performed by left-multiplying N by some properly-positioned 2×2 matrix and at the same time left-multiplying the “tracking matrix” P by the same 2×2 matrix. Column operations are similar, with left replaced by right and P by Q.

RowOp[i_, j_, mat_] := Module[{TT=II},
TT[[{i,j},{i,j}]] = mat;
NN=Simplify[TT.NN]; PP=Simplify[TT.PP]];
ColOp[i_, j_, mat_] := Module[{TT=II},
TT[[{i,j},{i,j}]] = mat;
NN=Simplify[NN.TT]; QQ=Simplify[QQ.TT]];

Swapping Rows and Columns

SwapRows[i_,j_] := RowOp[i,j,(({{0, 1}, {1, 0}}))];
SwapColumns[i_,j_] := ColOp[i,j,(({{0, 1}, {1, 0}}))];
SwapBoth[i_,j_] := (SwapRows[i,j]; SwapColumns[i,j];)

The “GCD” Trick

If q=gcd(a,b)=s a + t b, the equality (({{s, t}, {-b/q, a/q}}))(({{a}, {b}}))=(({{q}, {0}})) allows us to replace pairs of entries in the same column by their greatest common divisor (and a zero!), using invertible row operations. A similar trick works for rows.

?PolynomialExtendedGCD

GCDTrick[{i_,j_}, k_] := Module[{a,b,q,s,t},
{q,{s,t}} = PolynomialExtendedGCD[a=NN[[i,k]], b=NN[[j,k]],x];
RowOp[i,j,(({{s, t}, {-b/q, a/q}}))]];
GCDTrick[k_, {i_,j_}] := Module[{a,b,q,s,t},
{q,{s,t}} = PolynomialExtendedGCD[a=NN[[k,i]], b=NN[[k,j]],x];
ColOp[i,j,(({{s, -b/q}, {t, a/q}}))]];

Factoring Diagonal Entries

If 1=gcd(a,b)=s a + t b, the equality (({{s a, 1}, {-t b, 1}}))(({{1, 0}, {0, a b}}))(({{a, -b}, {t, s}}))=(({{a, 0}, {0, b}})) is an invertible row-column-operations proof of the isomorphism (R/(⟨a⟩))⊕(R/(⟨b⟩))≃(R/(⟨ab⟩)).

SplitToSum[i_,j_, a_, b_] := Module[{q,s,t, T1, T2},
{q,{s,t}} = PolynomialExtendedGCD[a, b, x];
If[q==1,RowOp[i,j,(({{s a, 1}, {-t b, 1}}))]; ColOp[i,j,(({{a, -b}, {t, s}}))]]];

The Jordan Trick

A repeated application of the identity (({{(p^(k-1)), -1}, {1, 0}})).(({{1, 0}, {0, (p^k)}})).(({{1, p}, {0, 1}}))=(({{(p^(-1+k)), 0}, {1, p}}))  will bring a matrix like (({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, (p^4)}})) to the “Jordan” form of (({{p, 0, 0, 0}, {1, p, 0, 0}, {0, 1, p, 0}, {0, 0, 1, p}})), using invertible row and column operations.

JordanTrick[i_, j_, p_, s_] := (RowOp[i,j,(({{(p^(s-1)), -1}, {1, 0}}))]; ColOp[i,j,(({{1, p}, {0, 1}}))]);

$Post=If[#=!=Null, #,
Print[StringForm["`1` `5` `2` . `3` . `4`",
NN//MatrixForm,PP//MatrixForm,MM//MatrixForm,QQ//MatrixForm,
If[Expand[NN]===Expand[PP.MM.QQ], "=", "≠"]
]]
]&;

Running the JCF Programs

Matrix 1 - 3x3, 3 eigenvalues.

(n=3; AA=(({{3, 0, 0}, {4, -2, -6}, {-2, 0, 1}})); PP=QQ = II = IdentityMatrix[n]; MM= x II - AA;  NN=PP.MM.QQ;)

SwapRows[1,2]

SwapColumns[2,3]

GCDTrick[{1,2},1]

GCDTrick[1,{1,2}]

GCDTrick[1,{1,3}]

GCDTrick[{1,3},1]

GCDTrick[2,{2,3}]

GCDTrick[{2,3},2]

GCDTrick[2,{2,3}]

SplitToSum[1,3,(-3+x), (-2+x+(x^2))]

Factor[-2+x+(x^2)]

SplitToSum[2,3,(-1+x), (2+x)]

MatrixForm /@ {Coefficient[NN, x, 1], BB = -Coefficient[NN, x, 0]}

(CC = Sum[
MatrixPower[BB, k].Coefficient[PP, x, k],
{k,0,n}
]) // MatrixForm

CC.AA.Inverse[CC] // MatrixForm

Matrix 2 - 3x3, one Jordan block.

(n=3; AA=(({{-(5/2), -11, (9/2)}, {-(1/2), 1, (1/2)}, {-(19/2), -16, (21/2)}})); PP=QQ = II = IdentityMatrix[n]; MM= x II - AA;  NN=PP.MM.QQ;)

(GCDTrick[1,{1,2}]; GCDTrick[1,{1,3}]; GCDTrick[{1,2},1]; GCDTrick[{1,3},1]; GCDTrick[2,{2,3}]; GCDTrick[{2,3},2];)

JordanTrick[2,3,x-3,3]

JordanTrick[1,2,x-3,2]

MatrixForm /@ {Coefficient[NN, x, 1], BB = -Coefficient[NN, x, 0]}

(CC = Sum[
MatrixPower[BB, k].Coefficient[PP, x, k],
{k,0,n}
]) // MatrixForm

CC.AA.Inverse[CC] // MatrixForm

Matrix 3 - 4x4, mixed Jordan form.

(n=4; AA=(({{1, -2, 0, -2}, {(1/4), (5/2), 0, (3/2)}, {(5/2), 5, 2, 3}, {(1/4), (1/2), 0, (3/2)}})); PP=QQ = II = IdentityMatrix[n]; MM= x II - AA;  NN=PP.MM.QQ;)

(GCDTrick[{1,2},1]; GCDTrick[1,{1,2}]; GCDTrick[1,{1,4}]; GCDTrick[{1,3},1];GCDTrick[{1,4},1]; GCDTrick[2,{2,3}]; GCDTrick[2,{2,4}]; GCDTrick[{2,3},2]; GCDTrick[{2,4},2]; GCDTrick[3, {3,4}];)

SwapBoth[1,3]

SplitToSum[2,4,(-1+x), (((-2+x))^2)]

SwapBoth[1,2]

JordanTrick[3,4,x-2, 2]

MatrixForm /@ {Coefficient[NN, x, 1], BB = -Coefficient[NN, x, 0]}

(CC = Sum[
MatrixPower[BB, k].Coefficient[PP, x, k],
{k,0,n}
]) // MatrixForm

CC.AA.Inverse[CC] // MatrixForm