Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following matrix: $P(s) :=$

\begin{bmatrix} s^2 & s-1 \\ s & s^2 \end{bmatrix}

How does one compute the Smith normal form of this matrix? I can't quite grasp the algorithm.

share|improve this question

1 Answer 1

Following the algorithm from Wilkinson's "The algebraic eigenvalue problem".

I will denote the current polynomial matrix as $P(\lambda)$ and its elements as $p_{ij}(\lambda)$, meaning that their values will change, with the final goal of having $P(\lambda)$ in the Smith form.

We start with

$$P(\lambda) = \begin{bmatrix} \lambda^2 & \lambda - 1 \\ \lambda & \lambda^2 \end{bmatrix}.$$

Pivot $(1,2)$.

  1. Pick one of the polynomials with the lowest degree.

    It seems that it would be easier to pick $p_{21}$ due to the step 3, but I'll go for $p_{12}$, as it seems to show better how that part is done. I'll later do the whole algorithm using $p_{21}$ as a pivot, and we'll see that it gets easier step 3, but is more complicated later on.

    $$P(\lambda) = \begin{bmatrix} \lambda^2 & \color{red}{\lambda - 1} \\ \lambda & \lambda^2 \end{bmatrix}.$$

  2. Swap rows/columns so that the pivot comes to the position $(1,1)$. In our case, we need to swap the first and the second column. We now have

    $$P(\lambda) = \begin{bmatrix} \color{red}{\lambda - 1} & \lambda^2 \\ \lambda^2 & \lambda \end{bmatrix}.$$

  3. Present all the polynomials in the first row and the first column (i.e., either $i=1$ or $j=1$) as $p_{ij}(\lambda) = p_{11}(\lambda) q_{ij}(\lambda) + r_{ij}(\lambda)$. In our case:

    $$P(\lambda) = \begin{bmatrix} \lambda - 1 & \color{red}{\lambda^2} \\ \color{red}{\lambda^2} & \lambda \end{bmatrix} = \begin{bmatrix} \lambda - 1 & \color{red}{(\lambda-1)(\lambda+1)+1} \\ \color{red}{(\lambda-1)(\lambda+1)+1} & \lambda \end{bmatrix}.$$

    So, in both cases, we got $q_{ij}(\lambda) = (\lambda+1)$ and $r_{ij}(\lambda) = 1$.

    Since $r_{ij} \not\equiv 0$, we need to fix that. Let us first deal with $r_{21}$. We substract $q_{21}$ times the first row from second row (the one in which is our $r_{21}$) and then interchange those two rows.

    First, we compute $q_{12}$ times the first row:

    $$q_{12}(\lambda) \begin{bmatrix} \lambda - 1 & \lambda^2 \end{bmatrix} = \begin{bmatrix} (\lambda+1)(\lambda - 1) & (\lambda+1)\lambda^2 \end{bmatrix} = \begin{bmatrix} \lambda^2 - 1 & \lambda^3 + \lambda^2 \end{bmatrix}.$$

    Substracting that from the second row, we get

    $$\begin{bmatrix} \lambda^2 & \lambda \end{bmatrix} - \begin{bmatrix} \lambda^2 - 1 & \lambda^3 + \lambda^2 \end{bmatrix} = \begin{bmatrix} 1 & -\lambda^3 - \lambda^2 + \lambda \end{bmatrix}.$$

    Now, exchanging it with the first row, we obtain

    $$P(\lambda) = \begin{bmatrix} 1 & -\lambda^3 - \lambda^2 + \lambda \\ \lambda - 1 & (\lambda-1)(\lambda+1)+1 \end{bmatrix}.$$

    This is to be repeated until all elements of the first row and the first column are divisible by $p_{11}$. In our case, $p_{11} \equiv 1$, so we got that, and we can write them in the form $p_{ij} = p_{11}q_{ij}$:

    $$P(\lambda) = \begin{bmatrix} 1 & \color{red}{1 \cdot (-\lambda^3 - \lambda^2 + \lambda)} \\ \color{red}{1 \cdot (\lambda - 1)} & (\lambda-1)(\lambda+1)+1 \end{bmatrix}.$$

  4. We now subtract the appropriate multiples of the first row from the rows $i=2,\dots,n$ and the appropriate multiples of the first column from the columns $ji=2,\dots,n$.

    Let us first find the multiple of the first row, to be subtracted from the second one, denoting it as ${\rm row}_2$. Since $p_{11} \equiv 1$, we see that ${\rm row}_2$ equals the first row multiplied by $p_{21}(\lambda)$:

    \begin{align*} {\rm row}_2 &= p_{21}(\lambda) \begin{bmatrix} 1 & -\lambda^3 - \lambda^2 + \lambda \end{bmatrix} = \begin{bmatrix} (\lambda - 1) \cdot 1 & (\lambda - 1) \cdot (-\lambda^3 - \lambda^2 + \lambda) \end{bmatrix} \\ &= \begin{bmatrix} \lambda - 1 & -\lambda^4 + 2 \lambda^2 - \lambda \end{bmatrix}.\end{align*}

    We now subtract these from the current second row and the current second column:

    \begin{align*} \begin{bmatrix} \lambda - 1 & \lambda^2 \end{bmatrix} - {\rm row}_2 &= \begin{bmatrix} \lambda - 1 & \lambda^2 \end{bmatrix} - \begin{bmatrix} \lambda - 1 & -\lambda^4 + 2 \lambda^2 - \lambda \end{bmatrix} \\ &= \begin{bmatrix} 0 & \lambda^4 - \lambda^2 + \lambda \end{bmatrix}. \\ \end{align*}

    Now, we need to be careful here, because we have just changed the second column and must not be working with the old one above. Observe our current $P(\lambda)$:

    $$P(\lambda) = \begin{bmatrix} 1 & -\lambda^3 - \lambda^2 + \lambda \\ \color{red}{0} & \color{red}{\lambda^4 - \lambda^2 + \lambda} \end{bmatrix}.$$

    Obviously, subtracting the first column times $(-\lambda^3 - \lambda^2 + \lambda)$ gives us

    $$P(\lambda) = \begin{bmatrix} 1 & \color{red}{0} \\ 0 & \color{red}{\lambda^4 - \lambda^2 + \lambda} \end{bmatrix}.$$

  5. Repeat the process on the bottom right principal submatrix of order $n-1$. In our case, $n = 2$, so the job is done, and the Smith form is

    $$P(\lambda) = \begin{bmatrix} 1 & 0 \\ 0 & \lambda^4 - \lambda^2 + \lambda \end{bmatrix}.$$

Pivot $(2,1)$.

Let us now do the same process, but picking $p_{21}(\lambda) = \lambda$ as the pivot in the first step.

  1. Pick one of the polynomials with the lowest degree.

    This time, we choose $p_{21}$.

    $$P(\lambda) = \begin{bmatrix} \lambda^2 & \lambda - 1 \\ \color{red}{\lambda} & \lambda^2 \end{bmatrix}.$$

  2. Swap rows/columns so that the pivot comes to the position $(1,1)$. In our case, we need to swap the first and the second row. We now have

    $$P(\lambda) = \begin{bmatrix} \color{red}{\lambda} & \lambda^2 \\ \lambda^2 & \lambda - 1 \end{bmatrix}.$$

  3. Present all the polynomials in the first row and the first column (i.e., either $i=1$ or $j=1$) as $p_{ij}(\lambda) = p_{11}(\lambda) q_{ij}(\lambda) + r_{ij}(\lambda)$. In our case:

    $$P(\lambda) = \begin{bmatrix} \lambda & \color{red}{\lambda^2} \\ \color{red}{\lambda^2} & \lambda - 1 \end{bmatrix} = \begin{bmatrix} \lambda & \color{red}{\lambda \cdot \lambda + 0} \\ \color{red}{\lambda \cdot \lambda + 0} & \lambda - 1 \end{bmatrix}.$$

    So, in both cases, we got $q_{ij}(\lambda) = \lambda$ and $r_{ij}(\lambda) = 0$. This is great, as we can skip the rest of the step 3. $\ddot\smile$

  4. We now subtract the appropriate multiples of the first row from the rows $i=2,\dots,n$ and the appropriate multiples of the first column from the columns $ji=2,\dots,n$.

    Let us first find the multiple of the first row, to be subtracted from the second one, denoting it as ${\rm row}_2$. Since $p_{11}(\lambda) = \lambda$ and $p_{21}(\lambda) = \lambda^2$, we see that ${\rm row}_2$ equals the first row multiplied by $(p_{21}/p_{11})(\lambda) = \lambda$:

    $${\rm row}_2 = (p_{21}/p_{11})(\lambda) \begin{bmatrix} \lambda & \lambda^2 \end{bmatrix} = \begin{bmatrix} \lambda^2 & \lambda^3 \end{bmatrix}.$$

    We now subtract this from the current second row:

    $$\begin{bmatrix} \lambda^2 & \lambda - 1 \end{bmatrix} - {\rm row}_2 = \begin{bmatrix} 0 & -\lambda^3 + \lambda - 1 \end{bmatrix}.$$

    Our current $P(\lambda)$ is

    $$P(\lambda) = \begin{bmatrix} \lambda & \lambda^2 \\ \color{red}{0} & \color{red}{-\lambda^3 + \lambda - 1} \end{bmatrix}.$$

    As before, we subtracting the first column's multiple will now just remove the nonzeroes in the first row.

    $$P(\lambda) = \begin{bmatrix} \lambda & \color{red}{0} \\ 0 & \color{red}{-\lambda^3 + \lambda - 1} \end{bmatrix}.$$

    Now, this may seem great, but notice that $p_{11} \nmid p_{22}$, so we need further corrections. This is done by adding the second row to the first one, repeating the above procedure. So, we get

    $$P(\lambda) = \begin{bmatrix} \color{red}{\lambda} & \color{red}{-\lambda^3 + \lambda - 1} \\ 0 & -\lambda^3 + \lambda - 1 \end{bmatrix} = \begin{bmatrix} \lambda & \color{red}{\lambda \cdot (-\lambda^2 + 1) + (-1)} \\ \color{red}{0} & -\lambda^3 + \lambda - 1 \end{bmatrix}.$$

    We see that $q_{12}(\lambda) = -\lambda^2 + 1$ and $r_{12}(\lambda) = 1$. We need to subtract the first column times $q_{12}(\lambda)$ from the second colum:

    $$P(\lambda) = \begin{bmatrix} \lambda & \color{red}{-1} \\ 0 & \color{red}{-\lambda^3 + \lambda - 1} \end{bmatrix}.$$

    Exchanging these two, we get

    $$P(\lambda) = \begin{bmatrix} -1 & \lambda \\ -\lambda^3 + \lambda - 1 & 0 \end{bmatrix}.$$

    After eliminating $p_{12}$, we have

    $$P(\lambda) = \begin{bmatrix} -1 & \color{red}{0} \\ -\lambda^3 + \lambda - 1 & \color{red}{-\lambda^4 + \lambda^2 - \lambda} \end{bmatrix}.$$

    Then we eliminate $p_{21}$:

    $$P(\lambda) = \begin{bmatrix} -1 & 0 \\ \color{red}{0} & \color{red}{-\lambda^4 + \lambda^2 - \lambda} \end{bmatrix}.$$

  5. Repeat the process on the bottom right principal submatrix of order $n-1$. In our case, as above, $n = 2$, so the job is almost done, as we have

    $$P(\lambda) = \begin{bmatrix} -1 & 0 \\ 0 & -\lambda^4 + \lambda^2 - \lambda \end{bmatrix}.$$

    For this to be a Smith form, we need the nonzero diagonal polynomials to be monic (i.e., have a leading coefficient equal to $1$). In our case, we do this by multiplying $P(\lambda)$ by $-1$. In a more generale case, we'd need to multiply it from either left or right by some constant diagonal matrix.

    Finally, we obtain

    $$P(\lambda) = \begin{bmatrix} 1 & 0 \\ 0 & \lambda^4 - \lambda^2 + \lambda \end{bmatrix}.$$

Concluding remarks

In both cases we got monic polynomials $p_{ii}$ such that $p_{11} \mid p_{22}$, and the degree of $(p_{11} \cdot p_{22})(\lambda)$ is $4 = 2 \cdot 2 = l \cdot n$, where $n$ is the order of the matrix and $l$ is the degree of $P$, as it should be. This is due to the fact that $\det P(\lambda)$ remained unchanged (in a more general case, it might get multiplied by a constant factor, in order to get the polynomials on the diagonal to become monic).

I have discarded all the info about the transformations. If one is to keep that, the row transformations are put in $E(\lambda)$, and the column transformations are put in $F(\lambda)$, to obtain

$$E(\lambda) P_{\text{starting}}(\lambda) F(\lambda) = P_{\text{final}}(\lambda).$$

where

$$ E(\lambda)=\begin{bmatrix}-1& 1 + \lambda - \lambda^2\\ -\lambda& -1 + \lambda + \lambda^2 - \lambda^3\end{bmatrix}$$

and

$$ F(\lambda)=\begin{bmatrix}1 - \lambda& -1 + \lambda - \lambda^2 - \lambda^3 + \lambda^4\\ 1& \lambda - \lambda^3\end{bmatrix}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.