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.