Please note: This PhD seminar will be given online.
Stavros Birmpilis, PhD candidate
David R. Cheriton School of Computer Science
Any nonsingular matrix $A \in \mathbb{Z}^{n\times n}$ is unimodularly equivalent to a unique diagonal matrix $S = diag(s_1, s_2, \ldots, s_n)$ in Smith form. The diagonal entries, the invariant factors of $A$, are positive with $s_1 \mid s_2 \mid \cdots \mid s_n$, and unimodularly equivalent means that there exist unimodular (with determinant ±1) matrices $U, V \in \mathbb{Z}^{n\times n}$ such that $UAV = S$.
We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an $A \in \mathbb{Z}^{n \times n}$, the algorithm requires $O(n^3 (\log n + \log ||A||)^2 (\log n)^2)$ bit operations using standard integer and matrix arithmetic, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.
200 University Avenue West
Waterloo, ON N2L 3G1
Canada