Talk:Smith normal form

Not Very Useful

The description given of the algorithm is a bit dense--not easy to understand. The example is not helpful because in every case, the entry that we wish to eliminate happens to be exactly a multiple of our pivot entry. What would happen if the example matrix was the following?

${\begin{pmatrix}2&3&4\\-6&6&12\\10&-4&-16\end{pmatrix}}$

The top center entry is 3, not 4, and is not a multiple of 2. The point I'm making is that clearly the example matrix is special in a way that makes the example computation unhelpful.

I'm currently studying this algorithm to learn it, when I figure it out and I think to come back then I'll try to update the article. If in the meantime someone who understands the algorithm was interested, I think it would be helpful to provide a clearer explanation along with an example on a more general matrix.

Thanks

128.208.36.26 (talk) 02:58, 27 April 2015 (UTC)

Smith Normal form not actually defined before algorithm

AbyssWyrm 11:48, 12 May 2008 (EDT)

Added example from aoh45's GFDL article at PlanetMath [1] -- The Anome 13:58, Oct 28, 2004 (UTC)

Please tell what GFDL means! (or remove it from the text) -- G. Rote 130.133.8.114 (talk) 15:56, 15 July 2009 (UTC)

Suggested merger of Elementary divisors with this article

The section "Results" in this article already has all (or close to all) the information present in the stub Elementary divisors listed in context for greater clarity. I suggest either merging the pages or just deleting the Elementary divisors stub altogether. However, in the interests of starting a friendly discussion on the topic and the fact that outright deletion is quite severe, I have simply suggested a simple merger as of the moment. Please discuss. Keith Davies Lehwald 20:43, 9 May 2006 (UTC)

Elementary divisors could be used for a lower-level discussion. Gene Ward Smith 09:48, 27 May 2006 (UTC)

Define Smith normal form precisely *before* launching into the algorithm

The article defines Smith normal form only very vaguely in the introduction, and then immediately launches into an algorithm for how to achieve this normal form.

It is necessary to define precisely what Smith normal form is *prior* to giving an algorithm for how to achieve it.Daqu (talk) 18:21, 31 January 2009 (UTC)

Done. 24.6.174.244 (talk) 04:44, 3 May 2009 (UTC)

Asymptotic complexity of algorithms?

Does anyone have any information about the asymptotic complexity of algorithms for computing Smith normal form? U25506 (talk) 22:24, 12 March 2010 (UTC)

The operation count complexity poorly reflects the running time in case the intermediate results grow to be very large numbers. Therefore, the useful bounds concern the bit-complexity. The bit-complexity bounds depend on both matrix dimensions and the invariant factors or the absolute values of the matrix entries, and are not as simple expressions as for floating point computations.

The first ones to prove a polynomial bound were Kannan and Bachem in "Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix", SIAM J. COMPUT. Vol. 8, No. 4, November 1979. The bound is slightly worse than quintic in nature. An improved bound was due to Chou and Collins a couple of years later. A textbook on the subject is K.C. Yap: Fundamental problems of algorithmic algebra, Oxford university press 1999. There are many more recent strategies (lower complexity with a very low probability of an incorrect solution, starting from some pre-processed form etc.). The bottom line: The bounds are still subject to active research, but the Chou-Collins bound is probably a useful general-purpose bound, if somebody is willing to include a discussion of the bounds to the article.

--Saku (talk) 09:04, 11 February 2014 (UTC)

SVD

Why is no reference made to singular value decomposition? It appears to be a generalization of SVD. Chris2crawford (talk) 12:22, 25 September 2011 (UTC)

The SVD entails notions of orthogonality and positivity and needs some form of algebraic closure (i.e., existence of eigenvalues for certain matrices/transformations) that are, in general, lacking over arbitrary fields. In contrast, the Smith normal form is attainable not just over arbitrary fields, but also more more generally over PIDs (e.g., the integers, or univariate polynomial rings over arbitrary fields). Alternative canonical forms more closely related to it than the SVD include the Frobenius normal form and the Hermite normal form.  PappyK (talk) 22:20, 3 April 2012 (UTC)

Integer entries / determinant one

Isn't an important point that the entries in S and T are integers, and that S and T have determinant 1 or -1? More generally, shouldn't this mean that S and T have entries from the PID, and their determinant be a unit? This is a consequence of the algorithm, but the only stated restrictions for S and T is that they are invertible. On the other hand, I wouldn't say that I am highly knowledgeable about this topic. 134.129.205.133 (talk) 15:53, 19 April 2012 (UTC) Tim

Clarification of definition

The matrix given by SAV would have dimension mxn, but the Smith form matrix is drawn in a way that implies it is square, with reference to diagonal entries also implying a square matrix. Please could this confusion be resolved. — Preceding unsigned comment added by 81.147.111.245 (talk) 07:33, 14 September 2014 (UTC)

Procedure described in Algorithm section does not keep the equality in the equation A’ = S’AT’

In the Algorithm section, it is stated that:

“The matrices S and T can be found by starting out with identity matrices of the appropriate size, and modifying S each time a row [my emphasis] operation is performed on A in the algorithm by the corresponding column operation (for example, if row i is added to row j of A, then column j should be subtracted from column i of S to retain the product invariant), and similarly modifying T for each column operation performed. Since row operations are left-multiplications and column operations are right-multiplications, this preserves the A’ = S’AT’ where A’, S’, T’ denote current values and A denotes the original matrix; eventually the matrices in this invariant become diagonal.”

In the equation A’ = S’AT’, the changing A’ matrix is on one side and the original unchanging A matrix is on the other, surrounded by the changing S’ and T’ unit matrices. If an elementary row operator is applied from the left to A’, the very same operator should be applied by the left on S’AT’, say to S’, in order to keep equality. And in case an elementary column operator is applied from the right on A’ the same should be applied on S’AT’, say on T’.

But the procedure currently described in the Algorithm section tells to apply opposite operations on each side. This will not preserve the equality of both sides, as it can be easily verified by building the S’ and T’ matrices for the matrix shown in the Example section and applying the algorithm. The equation will not hold true in any of the steps.

It can be seen at History page that this mistake appeared at first in the edition by Glox at 14:18, 21 July 2020 "Corrected an algorithmic error". — Preceding unsigned comment added by Miguelbbr (talk • contribs)

So it is proposed a reformulation of that part of the Algorithm section, as follows:

“The matrices S and T can be found by starting out with identity matrices of the appropriate size, and modifying S each time a row operation is performed on A’ in the algorithm by the same operation (for example, if row i is added to row j of A’, then row i should be added to column j of S to keep the equality). Similarly, modify the columns of T’ for each column operation performed in A’. This preserves the equality of both sides of the equation  A’ = S’AT’ where A’, S’, T’ denote current values and A denotes the original matrix. Eventually the matrix A’ will become diagonal and attain divisibility between the successive diagonal elements.”

Miguelbbr (talk) 02:37, 10 August 2022 (UTC)

Notation Needs to be Defined

The notation $x|y$ needs to be defined. I am pretty well versed in mathematics and I have no idea what it means in this context. 2620:0:2B33:5145:0:0:2:121 (talk) 15:25, 30 August 2023 (UTC)

It means x is a divisor of y. It is defined at https://en.wikipedia.org/wiki/Glossary_of_mathematical_symbols#Miscellaneous and https://en.wikipedia.org/wiki/Divisor Teepeemm (talk) 15:01, 19 September 2024 (UTC)

Unclear algorithm

In the section Algorithm this sentence appears:

"Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant $A'=S'\cdot A\cdot T'$ where $A',S',T'$ denote current values and $A$ denotes the original matrix; eventually the matrices in this invariant become diagonal."

It is entirely unclear what is meant by the word "invariant", since the matrix A' changes throughout the algorithm.

The use of the word "invariant" is far, far more confusing than helpful.