Smith normal form | EPFL Graph Search

In mathematics, the Smith normal form (sometimes abbreviated SNF) is a normal form that can be defined for any matrix (not necessarily square) with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith. Let A be a nonzero m×n matrix over a principal ideal domain R. There exist invertible and -matrices S, T (with coefficients in R) such that the product S A T is and the diagonal elements satisfy for all . This is the Smith normal form of the matrix A. The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as where (called i-th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix A and . The first goal is to find invertible square matrices and such that the product is diagonal. This is the hardest part of the algorithm. Once diagonality is achieved, it becomes relatively easy to put the matrix into Smith normal form. Phrased more abstractly, the goal is to show that, thinking of as a map from (the free -module of rank ) to (the free -module of rank ), there are isomorphisms and such that has the simple form of a diagonal matrix. The matrices and can be found by starting out with identity matrices of the appropriate size, and modifying each time a row operation is performed on in the algorithm by the corresponding column operation (for example, if row is added to row of , then column should be subtracted from column of to retain the product invariant), and similarly modifying for each column operation performed.

Non-normal forms

Yves-Marie François Ducimetière

In this thesis, we propose to formally derive amplitude equations governing the weakly nonlinear evolution of non-normal dynamical systems, when they respond to harmonic or stochastic forcing, or to an initial condition. This approach reconciles the non-mo ...

EPFL2024

Validating functional redundancy with mixed generative adversarial networks

Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Trung-Dung Hoang

Data redundancy has been one of the most important problems in data-intensive applications such as data mining and machine learning. Removing data redundancy brings many benefits in efficient data updating, effective data storage, and error-free query proc ...

ELSEVIER2023

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022