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

JCF Tricks and Programs

Pensieve header: 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}}))]);