Combinatorics, Special Functions and Computer Algebra
A workshop at the occasion of Peter Paule's 60th birthday
Eigenvalues, invariant factors and random integer matrices
Mark Giesbrecht, University of Waterloo
Abstract: Integer matrices are often characterized by the lattice of
combinations of their rows or columns. This is captured nicely by the
Smith canonical form, a diagonal matrix of invariant factors, to which
any integer matrix can be transformed through left and right
multiplication by unimodular matrices. Algorithms for computing Smith
forms have seen dramatic improvements over the past 40 years, but
effective algorithms for large sparse matrices still need improvement.
Integer matrices also possess complex eigenvalues and eigenvectors,
and every such matrix is similar to a unique one in Jordan canonical
form. There is a wealth of numerical methods for computing
eigenvalues, and Krylov-type algorithms are effective for sparse
matrices.
It would seem a priori that the invariant factors and the eigenvalues
would have little to do with each other. Yet we will show that for
"almost all" matrices the invariant factors and the eigenvalues are
equivalent under a p-adic valuation, in a very precisely counted sense.
A much-hoped-for link is then explored for fast computation of Smith
forms of sparse integer matrices, via the better understood algorithms
for computing eigenvalues and effective preconditioning.
This is joint work with Mustafa Elsheikh.