LJKDeterministic Models and Algorithms: CASYS Seminar

On Thursday November 9 2017 at 9h30 in Room 106  IMAG Building

Seminary of Mr Mark GIESBRECHT (University of Waterloo)

Eigenvalues, invariant and random integer matrices

Summary

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 have proven somewhat elusive.
Integer matrices can also be viewed as complex matrices, with eigenvalues and eigenvectors, and every such matrix is similar to a unique one in Jordan canonical form. There is a wealth of effective numerical and symbolic methods for computing eigenvalues. Krylovtype algorithms are also very useful for computing with sparse matrices, even in the symbolic domain or over finite fields.
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 equal under a padic valuation, in a very precise sense.
A muchhopedfor link is explored for fast computation of Smith forms of sparse integer matrices, via the better understood algorithms for computing eigenvalues and effective preconditioning. All the methods are elementary and no particular background beyond linear algebra will be assumed.
