# Normal form (for matrices)

The normal form of a matrix $A$ is a matrix $N$ of a pre-assigned special form obtained from $A$ by means of transformations of a prescribed type. One distinguishes various normal forms, depending on the type of transformations in question, on the domain $K$ to which the coefficients of $A$ belong, on the form of $A$, and, finally, on the specific nature of the problem to be solved (for example, on the desirability of extending or not extending $K$ on transition from $A$ to $N$, on the necessity of determining $N$ from $A$ uniquely or with a certain amount of arbitrariness). Frequently, instead of "normal form" one uses the term "canonical form of a matrixcanonical form" . Among the classical normal forms are the following. (Henceforth $M _ {m \times n } ( K)$ denotes the set of all matrices of $m$ rows and $n$ columns with coefficients in $K$.)

## The Smith normal form.

Let $K$ be either the ring of integers $\mathbf Z$ or the ring $F[ \lambda ]$ of polynomials in $\lambda$ with coefficients in a field $F$. A matrix $B \in M _ {m \times n } ( K)$ is called equivalent to a matrix $A \in M _ {m \times n } ( K)$ if there are invertible matrices $C \in M _ {m \times m } ( K)$ and $D \in M _ {n \times n } ( K)$ such that $B = C A D$. Here $B$ is equivalent to $A$ if and only if $B$ can be obtained from $A$ by a sequence of elementary row-and-column transformations, that is, transformations of the following three types: a) permutation of the rows (or columns); b) addition to one row (or column) of another row (or column) multiplied by an element of $K$; or c) multiplication of a row (or column) by an invertible element of $K$. For transformations of this kind the following propositions hold: Every matrix $A \in M _ {m \times n } ( K)$ is equivalent to a matrix $N \in M _ {m \times n } ( K)$ of the form

$$N = \left \| \begin{array}{cccccccc} d _ {1} &{} &{} &{} &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} &{} &{} &{} \\ {} &{} &\cdot &{} &{} &{} &{} &{} \\ {} &{} &{} &d _ {r} &{} &{} &{} &{} \\ {} &{} &{} &{} & 0 &{} &{} &{} \\ {} &{} &{} &{} &{} &\cdot &{} &{} \\ {} &{} &{} &{} &{} &{} &\cdot &{} \\ 0 &{} &{} &{} &{} &{} &{} & 0 \\ \end{array} \right \| ,$$

where $d _ {i} \neq 0$ for all $i$; $d _ {i}$ divides $d _ {i+1}$ for $i = 1 \dots r - 1$; and if $K = \mathbf Z$, then all $d _ {i}$ are positive; if $K = F [ \lambda ]$, then the leading coefficients of all polynomials $d _ {i}$ are 1. This matrix is called the Smith normal form of $A$. The $d _ {i}$ are called the invariant factors of $A$ and the number $r$ is called its rank. The Smith normal form of $A$ is uniquely determined and can be found as follows. The rank $r$ of $A$ is the order of the largest non-zero minor of $A$. Suppose that $1 \leq j \leq r$; then among all minors of $A$ of order $j$ there is at least one non-zero. Let $\Delta _ {j}$, $j = 1 \dots r$, be the greatest common divisor of all non-zero minors of $A$ of order $j$( normalized by the condition $\Delta _ {j} > 0$ for $K = \mathbf Z$ and such that the leading coefficient of $\Delta _ {j}$ is 1 for $K = F [ \lambda ]$), and let $\Delta _ {0} = 1$. Then $d _ {j} = \Delta _ {j} / \Delta _ {j-1}$, $j = 1 \dots r$. The invariant factors form a full set of invariants of the classes of equivalent matrices: Two matrices in $M _ {m \times n } ( K)$ are equivalent if and only if their ranks and their invariant factors with equal indices are equal.

The invariant factors $d _ {1} \dots d _ {r}$ split (in a unique manner, up to the order of the factors) into the product of powers of irreducible elements $e _ {1} \dots e _ {s}$ of $K$( which are positive integers $> 1$ when $K = \mathbf Z$, and polynomials of positive degree with leading coefficient 1 when $K = F [ \lambda ]$):

$$d _ {i} = \ e _ {1} ^ {n _ {i1} } \dots e _ {s} ^ {n _ {is} } ,\ \ i = 1 \dots r ,$$

where the $n _ {ij}$ are non-negative integers. Every factor $e _ {j} ^ {n _ {ij} }$ for which $n _ {ij} > 0$ is called an elementary divisor of $A$( over $K$). Every elementary divisor of $A$ occurs in the set ${\mathcal E} _ {A , K }$ of all elementary divisors of $A$ with multiplicity equal to the number of invariant factors having this divisor in their decompositions. In contrast to the invariant factors, the elementary divisors depend on the ring $K$ over which $A$ is considered: If $K = F [ \lambda ]$, $\widetilde{F}$ is an extension of $F$ and $\widetilde{K} = \widetilde{F} [ \lambda ]$, then, in general, a matrix $A \in M _ {m \times n } ( K) \subset M _ {m \times n } ( \widetilde{K} )$ has distinct elementary divisors (but the same invariant factors), depending on whether $A$ is regarded as an element of $M _ {m \times n } ( K)$ or of $M _ {m \times n } ( \widetilde{K} )$. The invariant factors can be recovered from the complete collection of elementary divisors, and vice versa.

For a practical method of finding the Smith normal form see, for example, .

The main result on the Smith normal form was obtained for $K = \mathbf Z$( see ) and $K = F [ \lambda ]$( see ). With practically no changes, the theory of Smith normal forms goes over to the case when $K$ is any principal ideal ring (see , ). The Smith normal form has important applications; for example, the structure theory of finitely-generated modules over principal ideal rings is based on it (see , ); in particular, this holds for the theory of finitely-generated Abelian groups and theory of the Jordan normal form (see below).

## The natural normal form

Let $K$ be a field. Two square matrices $A , B \in M _ {n \times n } ( K)$ are called similar over $K$ if there is a non-singular matrix $C \in M _ {n \times n } ( K)$ such that $B = C ^ {-1} A C$. There is a close link between similarity and equivalence: Two matrices $A , B \in M _ {n \times n } ( K)$ are similar if and only if the matrices $\lambda E - A$ and $\lambda E - B$, where $E$ is the identity matrix, are equivalent. Thus, for the similarity of $A$ and $B$ it is necessary and sufficient that all invariant factors, or, what is the same, the collection of elementary divisors over $K [ \lambda ]$ of $\lambda E - A$ and $\lambda E - B$, are the same. For a practical method of finding a $C$ for similar matrices $A$ and $B$, see , .

The matrix $\lambda E - A$ is called the characteristic matrix of $A \in M _ {n \times n } ( K)$, and the invariant factors of $\lambda E - A$ are called the similarity invariants of $A$; there are $n$ of them, say $d _ {1} \dots d _ {n}$. The polynomial $d _ {n}$ is the determinant of $\lambda E - A$ and is called the characteristic polynomial of $A$. Suppose that $d _ {1} = \dots = d _ {q} = 1$ and that for $j \geq q + 1$ the degree of $d _ {j}$ is greater than 1. Then $A$ is similar over $K$ to a block-diagonal matrix $N _ {1} \in M _ {n \times n } ( K)$ of the form

$$N _ {1} = \left \| \begin{array}{ccccc} L ( d _ {q+1} ) &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} \\ {} &{} &\cdot &{} &{} \\ {} &{} &{} &\cdot &{} \\ 0 &{} &{} &{} &L ( d _ {n} ) \\ \end{array} \right \| ,$$

where $L ( f )$ for a polynomial

$$f = \lambda ^ {p} + \alpha _ {1} \lambda ^ {p-1} + \dots + \alpha _ {p}$$

denotes the so-called companion matrix

$$L ( f ) = \ \left \| \begin{array}{cccccc} 0 & 1 & 0 &\dots & 0 & 0 \\ 0 & 0 & 1 &\dots & 0 & 0 \\ \cdot &\cdot &\cdot &\dots &\cdot &\cdot \\ 0 & 0 & 0 &\dots & 0 & 1 \\ {- \alpha _ {p} } &{- \alpha _ {p-1} } &{- \alpha _ {p-2} } &\dots &{- \alpha _ {2} } &{- \alpha _ {1} } \\ \end{array} \right \| .$$

The matrix $N _ {1}$ is uniquely determined from $A$ and is called the first natural normal form of $A$( see , ).

Now let ${\mathcal E} _ {A , K [ \lambda ] }$ be the collection of all elementary divisors of $\lambda E - A$. Then $A$ is similar over $K$ to a block-diagonal matrix $N _ {2}$( cf. Block-diagonal operator) whose blocks are the companion matrices of all elementary divisors $e _ {j} ^ {n _ {ij} } \in {\mathcal E} _ {A , K [ \lambda ] }$ of $\lambda E - A$:

$$N _ {2} = \ \left \| \begin{array}{ccccc} \cdot &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} \\ {} &{} &L ( e _ {j} ^ {n _ {ij} } ) &{} &{} \\ {} &{} &{} &\cdot &{} \\ {} &{} &{} &{} &{} \\ 0 &{} &{} &{} &\cdot \\ \end{array} \right \| .$$

The matrix $N _ {2}$ is determined from $A$ only up to the order of the blocks along the main diagonal; it is called the second natural normal form of $A$( see , ), or its Frobenius, rational or quasi-natural normal form (see ). In contrast to the first, the second natural form changes, generally speaking, on transition from $K$ to an extension.

## The Jordan normal form.

Let $K$ be a field, let $A \in M _ {n \times n } ( K)$, and let ${\mathcal E} _ {A , K [ \lambda ] } = \{ e _ {i} ^ {n _ {ij} } \}$ be the collection of all elementary divisors of $\lambda E - A$ over $K [ \lambda ]$. Suppose that $K$ has the property that the characteristic polynomial $d _ {n}$ of $A$ splits in $K [ \lambda ]$ into linear factors. (This is so, for example, if $K$ is the field of complex numbers or, more generally, any algebraically closed field.) Then every one of the polynomials $e _ {i}$ has the form $\lambda - a _ {i}$ for some $a _ {i} \in K$, and, accordingly, $e _ {i} ^ {n _ {ij} }$ has the form $( \lambda - a _ {i} ) ^ {n _ {ij} }$. The matrix $J ( f )$ in $M _ {s \times s } ( K)$ of the form

$$J ( f ) = \ \left \| \begin{array}{cccccc} a & 1 &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} &{} \\ {} &{} &\cdot &{} &{} &{} \\ {} &{} &{} &\cdot &{} &{} \\ {} &{} &{} &{} &\cdot & 1 \\ 0 &{} &{} &{} &{} & a \\ \end{array} \right \| ,$$

where $f = ( \lambda - a ) ^ {s}$, $a \in K$, is called the hypercompanion matrix of $f$( see ) or the Jordan block of order $s$ with eigenvalue $a$. The following fundamental proposition holds: A matrix $A$ is similar over $K$ to a block-diagonal matrix $J \in M _ {n \times n } ( K)$ whose blocks are the hypercompanion matrices of all elementary divisors of $\lambda E - A$:

$$J = \left \| \begin{array}{ccccc} \cdot &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} \\ {} &{} &J ( e _ {i} ^ {n _ {ij} } ) &{} &{} \\ {} &{} &{} &\cdot &{} \\ 0 &{} &{} &{} &\cdot \\ \end{array} \right \| .$$

The matrix $J$ is determined only up to the order of the blocks along the main diagonal; it is a Jordan matrix and is called the Jordan normal form of $A$. If $K$ does not have the property mentioned above, then $A$ cannot be brought, over $K$, to the Jordan normal form (but it can over a finite extension of $K$). See  for information about the so-called generalized Jordan normal form, reduction to which is possible over any field $K$.

Apart from the various normal forms for arbitrary matrices, there are also special normal forms of special matrices. Classical examples are the normal forms of symmetric and skew-symmetric matrices. Let $K$ be a field. Two matrices $A , B \in M _ {n \times n } ( K)$ are called congruent (see ) if there is a non-singular matrix $C \in M _ {n \times n } ( K)$ such that $B = C ^ {T} A C$. Normal forms under the congruence relation have been investigated most thoroughly for the classes of symmetric and skew-symmetric matrices. Suppose that $\mathop{\rm char} K \neq 2$ and that $A$ is skew-symmetric, that is, $A ^ {T} = - A$. Then $A$ is congruent to a uniquely determined matrix $H$ of the form

$$H = \left \| \begin{array}{rcrccrcccc} 0 & 1 &{} &{} &{} &{} &{} &{} &{} &{} \\ - 1 & 0 &{} &{} &{} &{} &{} &{} &{} &{} \\ {} &{} & 0 & 1 &{} &{} &{} &{} &{} &{} \\ {} &{} &- 1 & 0 &{} &{} &{} &{} &{} &{} \\ {} &{} &{} &{} &\cdot &{} &{} &{} &{} &{} \\ {} &{} &{} &{} &{} & 0 & 1 &{} &{} &{} \\ {} &{} &{} &{} &{} &- 1 & 0 &{} &{} &{} \\ {} &{} &{} &{} &{} &{} &{} & 0 &{} &{} \\ {} &{} &{} &{} &{} &{} &{} &{} &\cdot &{} \\ {} &{} &{} &{} &{} &{} &{} &{} &{} & 0 \\ \end{array} \right \| ,$$

which can be regarded as the normal form of $A$ under congruence. If $A$ is symmetric, that is, $A ^ {T} = A$, then it is congruent to a matrix $D$ of the form

$$D = \left \| \begin{array}{cccccccc} \epsilon _ {1} &{} &{} &{} &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} &{} &{} &{} \\ {} &{} &\cdot &{} &{} &{} &{} &{} \\ {} &{} &{} &\epsilon _ {r} &{} &{} &{} &{} \\ {} &{} &{} &{} & 0 &{} &{} &{} \\ {} &{} &{} &{} &{} &\cdot &{} &{} \\ {} &{} &{} &{} &{} &{} &\cdot &{} \\ 0 &{} &{} &{} &{} &{} &{} & 0 \\ \end{array} \right \| ,$$

where $\epsilon _ {1} \neq 0$ for all $i$. The number $r$ is the rank of $A$ and is uniquely determined. The subsequent finer choice of the $\epsilon _ {i}$ depends on the properties of $K$. Thus, if $K$ is algebraically closed, one may assume that $\epsilon _ {1} = \dots = \epsilon _ {r} = 1$; if $K$ is the field of real numbers, one may assume that $\epsilon _ {1} = \dots \epsilon _ {p} = 1$ and $\epsilon _ {p+1} = \dots = \epsilon _ {r} = - 1$ for a certain $p$. $D$ is uniquely determined by these properties and can be regarded as the normal form of $A$ under congruence. See ,  and Quadratic form for information about the normal forms of symmetric matrices for a number of other fields, and also about Hermitian analogues of this theory.

A common feature in the theories of normal forms considered above (and also in others) is the fact that the admissible transformations over the relevant set of matrices are determined by the action of a certain group, so that the classes of matrices that can be carried into each other by means of these transformations are the orbits (cf. Orbit) of this group, and the appropriate normal form is the result of selecting in each orbit a certain canonical representative. Thus, the classes of equivalent matrices are the orbits of the group $G = \mathop{\rm GL} _ {m} ( K) \times \mathop{\rm GL} _ {n} ( K)$( where $\mathop{\rm GL} _ {s} ( K)$ is the group of invertible square matrices of order $s$ with coefficients in $K$), acting on $M _ {m \times n } ( K)$ by the rule $A \rightarrow C ^ {-1} A D$, where $( C , D ) \in G$. The classes of similar matrices are the orbits of $\mathop{\rm GL} _ {n} ( K)$ on $M _ {n \times n } ( K)$ acting by the rule $A \rightarrow C ^ {-1} A C$, where $C \in \mathop{\rm GL} _ {n} ( K)$. The classes of congruent symmetric or skew-symmetric matrices are the orbits of the group $\mathop{\rm GL} _ {n} ( K)$ on the set of all symmetric or skew-symmetric matrices of order $n$, acting by the rule $A \rightarrow C ^ {T} A C$, where $C \in \mathop{\rm GL} _ {n} ( K)$. From this point of view every normal form is a specific example of the solution of part of the general problem of orbital decomposition for the action of a certain transformation group.

How to Cite This Entry:
Normal form (for matrices). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Normal_form_(for_matrices)&oldid=51503
This article was adapted from an original article by V.L. Popov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article