Smith normal form of matrix over $Z$? I was wondering if someone could help me find the Smith normal form of the matrix A over $Z$ defined as follows:
$A =
\begin{bmatrix}
1 & 1 & 1 & 1 & 1\\
1 & 2 & 4 & 8 & 16\\
1 & 3 & 9 & 27 & 81\\
1 & 4 & 16 & 64 & 256\\
1 & 5 & 25 & 125 & 625\\
\end{bmatrix}$
Clearly this is the same as:
$\begin{bmatrix}
1 & 1 & 1 & 1 & 1\\
1 & 2 & 2^2 & 2^3 & 12^4\\
1 & 3 & 3^2 & 3^3 & 3^4\\
1 & 4 & 4^2 & 4^3 & 4^5\\
1 & 5 & 5^2 & 5^3 & 5^4\\
\end{bmatrix}$
Is there some "trick" I am unaware of? Through row and column operations I just get stuck at a matrix looking like this:
$\begin{bmatrix}
1 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 1 & 1\\
\end{bmatrix}$
 A: The invariance of Fitting ideals probably helps. The matrix and some of its submatrices are 'Vandermonde' matrices so their determinants are easy to calcualate.
I think the SNF is diag(0!,1!,2!,3!,4!), a pattern that generalises with n instead of 5. We can show this sort of inductively, using that such a matrix has determinant 1!2!...(n-1)!. Please ask if you want more details.
Edit with full details:
The result on Vandermonde determinants can be found on Wikipedia. The easiest way to prove it is to work in $\mathbb{Z}[X_1,...,X_n]$, note that setting $X_i = X_j$ gives a zero determinant, so by the factor the lcm of these terms, $\prod_{i<j}(X_j-X_i)$ divides the determinant. Note that so far this works for any k x k submatrix of a Vandermonde matrix, where we replace $X_1,...,X_n$ with the appropriate subset of size k. Comparing degrees, we get for the whole matrix that the determinant is actually equal to $\prod_{i<j}(X_j-X_i)$.
So in our case, where we set $X_i = i$, the determinant is  $\prod_{i<j}(j-i)$ =  $\prod_{j}(j-1)!$.
And any k x k submatrix has determinant a multiple of  $\prod_{i<j}(a_j-a_i)$, for some $\{a_1,...,a_k\} \subset \{1,...,n\}$. I claim this is a multiple of  $\prod_{j=1}^{k}(j-1)!$. Indeed let $p$ be a prime dividing the latter. Let $a$ be the largest number such that $p^a < k$. Note by the pigeonhole principle some pair, wlog  $a_k,a_{k-1}$, has difference a multiple of $p^a$. Discard $a_k$ and make the same argumement with $k \mapsto k-1$. Once p^a = k, replace a with a-1 and make the same argument, etc. I haven't explained this well but this process gives you distinct pairs from the $a_i$'s the product of whose differences is a multiple of p with the same multiplicity as in the prime factorisation of $\prod_{j=1}^{k}(j-1)!$.
Therefore applying for each prime factor, we get that $\prod_{j=1}^{k}(j-1)!$ divides $\prod_{i<j}(a_j-a_i)$ and hence the determinant of the k x k submatrix, as we wanted to show. And if the k x k submatrix is the top-left one, we have equality.
So the Fitting ideals are $\text{Fit}_k = (\prod_{j=1}^{k}(j-1)!)$, and so $d_1...d_k = \prod_{j=1}^{k}(j-1)!$. From here we deduce the invariant factors $d_k = (k-1)!$ for each k.
A: Define
$$P := \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 \\ -1 & 3 & -3 & 1 & 0 \\ 1 & -4 & 6 & -4 & 1 \end{bmatrix}.$$
Then
$$P A = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 3 & 7 & 15 \\ 0 & 0 & 2 & 12 & 50 \\ 0 & 0 & 0 & 6 & 60 \\ 0 & 0 & 0 & 0 & 24\end{bmatrix} =
\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 24\end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 3 & 7 & 15 \\ 0 & 0 & 1 & 6 & 25 \\ 0 & 0 & 0 & 1 & 10 \\ 0 & 0 & 0 & 0 & 1\end{bmatrix} =: DQ.$$
Now since $P$ and $Q$ are unimodular matrices by inspection, it follows that $D$ is the Smith normal form of $A$.
This should generalize nicely to higher values of $n$: if $P$ is the matrix whose $i,j$ element is $(-1)^{i+j} \binom{i-1}{j-1}$, then the $i,j$ element of $PA$ will be $(\Delta^{i-1} x^{j-1}) |_{x = 1}$, which is equal to 0 if $i > j$; equal to $(i-1)!$ if $i = j$; and divisible by $(i-1)!$ if $i < j$.  Therefore, we will again be able to get a similar factorization $PA = DQ$ where $D$ is diagonal with $D_{ii} = (i-1)!$; and $Q$ is upper triangular with 1 on the diagonal and therefore unimodular.
