The ZigZag function applies a sequence of similarity transformations to the $nxn$ mod m Matrix A to obtain the ZigZag form of A.

A ZigZag form is an almost block diagonal structure having fewer than $2n$ nonzero entries.

A ZigZag form can be used to obtain the Smith normal form and the Frobenius form of a Matrix. The Frobenius form of a Matrix is the same as the Frobenius form of its ZigZag form.

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form ZigZag(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][ZigZag](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\:$

$p≔97$

$p≔97$

$A≔\mathrm{Mod}\left(p\,\mathrm{Matrix}\left(5\,5\,\left(i\,j\right)\mapsto \mathbf{if}i\le j\mathbf{then}\mathrm{rand}\left(\right)\mathbf{else}0\mathbf{end}\mathbf{if}\right)\,\mathrm{integer}\left[\right]\right)$

$A≔\left[\begin{array}{ccccc}77& 96& 10& 86& 58\\ 0& 36& 80& 22& 44\\ 0& 0& 39& 60& 39\\ 0& 0& 0& 43& 12\\ 0& 0& 0& 0& 55\end{array}\right]$

$\mathrm{A2}≔\mathrm{Copy}\left(p\,A\right)\:$

$\mathrm{ZigZag}\left(p\,\mathrm{A2}\right)\:$

$\mathrm{A2}$

$\left[\begin{array}{ccccc}77& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 44& 8& 36& 76\end{array}\right]$

$\mathrm{Frobenius}\left(\mathrm{A2}\right)\mathbf{mod}p,\mathrm{Frobenius}\left(A\right)\mathbf{mod}p$

$\left[\begin{array}{ccccc}0& 0& 0& 0& 7\\ 1& 0& 0& 0& 10\\ 0& 1& 0& 0& 49\\ 0& 0& 1& 0& 4\\ 0& 0& 0& 1& 56\end{array}\right],\left[\begin{array}{ccccc}0& 0& 0& 0& 7\\ 1& 0& 0& 0& 10\\ 0& 1& 0& 0& 49\\ 0& 0& 1& 0& 4\\ 0& 0& 0& 1& 56\end{array}\right]$