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.[edit]

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=CAD$. 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=\Vert \begin{array}{cccccccc}{d}_1& & & & & & & 0\\ & \cdot & & & & & & \\ & & \cdot & & & & & \\ & & & d_r& & & & \\ & & & & 0& & & \\ & & & & & \cdot & & \\ & & & & & & \cdot & \\ 0& & & & & & & 0\end{array}\Vert ,$$

where $d_i\ne 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\le j\le r$; then among all minors of $A$ of order $j$ there is at least one non-zero. Let ${\mathrm{\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 ${\mathrm{\Delta }}_j>0$ for $K=\mathbf{Z}$ and such that the leading coefficient of ${\mathrm{\Delta }}_j$ is 1 for $K=F[\lambda ]$), and let ${\mathrm{\Delta }}_0=1$. Then $d_j={\mathrm{\Delta }}_j/{\mathrm{\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 ]$, $\tilde{F}$ is an extension of $F$ and $\tilde{K}=\tilde{F}[\lambda ]$, then, in general, a matrix $A\in M_{m\times n}(K)\subset M_{m\times n}(\tilde{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}(\tilde{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, [1].

The main result on the Smith normal form was obtained for $K=\mathbf{Z}$( see [7]) and $K=F[\lambda ]$( see [8]). With practically no changes, the theory of Smith normal forms goes over to the case when $K$ is any principal ideal ring (see [3], [6]). 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 [3], [6]); 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[edit]

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}AC$. 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 [1], [4].

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=\cdots =d_q=1$ and that for $j\ge 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=\Vert \begin{array}{ccccc}L(d_{q+1})& & & & 0\\ & \cdot & & & \\ & & \cdot & & \\ & & & \cdot & \\ 0& & & & L(d_n)\end{array}\Vert ,$$

where $L(f)$ for a polynomial

$$f={\lambda }^p+{\alpha }_1{\lambda }^{p-1}+\cdots +{\alpha }_p$$

denotes the so-called companion matrix

$$L(f)=\Vert \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}\Vert .$$

The matrix $N_1$ is uniquely determined from $A$ and is called the first natural normal form of $A$( see [1], [2]).

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=\Vert \begin{array}{ccccc}\cdot & & & & 0\\ & \cdot & & & \\ & & L(e_j^{n_{ij}})& & \\ & & & \cdot & \\ & & & & \\ 0& & & & \cdot \end{array}\Vert .$$

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 [1], [2]), or its Frobenius, rational or quasi-natural normal form (see [4]). In contrast to the first, the second natural form changes, generally speaking, on transition from $K$ to an extension.

The Jordan normal form.[edit]

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)=\Vert \begin{array}{cccccc}a& 1& & & & 0\\ & \cdot & & & & \\ & & \cdot & & & \\ & & & \cdot & & \\ & & & & \cdot & 1\\ 0& & & & & a\end{array}\Vert ,$$

where $f=(\lambda -a{)}^s$, $a\in K$, is called the hypercompanion matrix of $f$( see [1]) 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=\Vert \begin{array}{ccccc}\cdot & & & & 0\\ & \cdot & & & \\ & & J(e_i^{n_{ij}})& & \\ & & & \cdot & \\ 0& & & & \cdot \end{array}\Vert .$$

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 [4] 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 [1]) if there is a non-singular matrix $C\in M_{n\times n}(K)$ such that $B=C^{T}AC$. Normal forms under the congruence relation have been investigated most thoroughly for the classes of symmetric and skew-symmetric matrices. Suppose that $\mathrm{char}K\ne 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=\Vert \begin{array}{rcrccrcccc}0& 1& & & & & & & & \\ -1& 0& & & & & & & & \\ & & 0& 1& & & & & & \\ & & -1& 0& & & & & & \\ & & & & \cdot & & & & & \\ & & & & & 0& 1& & & \\ & & & & & -1& 0& & & \\ & & & & & & & 0& & \\ & & & & & & & & \cdot & \\ & & & & & & & & & 0\end{array}\Vert ,$$

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=\Vert \begin{array}{cccccccc}{ϵ}_1& & & & & & & 0\\ & \cdot & & & & & & \\ & & \cdot & & & & & \\ & & & {ϵ}_r& & & & \\ & & & & 0& & & \\ & & & & & \cdot & & \\ & & & & & & \cdot & \\ 0& & & & & & & 0\end{array}\Vert ,$$

where ${ϵ}_1\ne 0$ for all $i$. The number $r$ is the rank of $A$ and is uniquely determined. The subsequent finer choice of the ${ϵ}_i$ depends on the properties of $K$. Thus, if $K$ is algebraically closed, one may assume that ${ϵ}_1=\cdots ={ϵ}_r=1$; if $K$ is the field of real numbers, one may assume that ${ϵ}_1=\dots {ϵ}_p=1$ and ${ϵ}_{p+1}=\cdots ={ϵ}_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 [6], [10] 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={\mathrm{GL}}_m(K)\times {\mathrm{GL}}_n(K)$( where ${\mathrm{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\to C^{-1}AD$, where $(C,D)\in G$. The classes of similar matrices are the orbits of ${\mathrm{GL}}_n(K)$ on $M_{n\times n}(K)$ acting by the rule $A\to C^{-1}AC$, where $C\in {\mathrm{GL}}_n(K)$. The classes of congruent symmetric or skew-symmetric matrices are the orbits of the group ${\mathrm{GL}}_n(K)$ on the set of all symmetric or skew-symmetric matrices of order $n$, acting by the rule $A\to C^{T}AC$, where $C\in {\mathrm{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.

References[edit]

Comments[edit]

The Smith canonical form and a canonical form related to the first natural normal form are of substantial importance in linear control and system theory [a1], [a2]. Here one studies systems of equations $\dot{x}=Ax+Bu$, $x\in {\mathbf{R}}^n$, $u\in {\mathbf{R}}^m$, and the similarity relation is: $(A,B)\sim (SA{S}^{-1},SB)$. A pair of matrices $A\in {\mathbf{R}}^{n\times n}$, $B\in {\mathbf{R}}^{n\times m}$ is called completely controllable if the rank of the block matrix

$$(B,AB\dots A^{n}B)=R(A,B)$$

is $n$. Observe that $R(SA{S}^{-1},SB)=SR(A,B)$, so that a canonical form can be formed by selecting $n$ independent column vectors from $R(A,B)$. This can be done in many ways. The most common one is to test the columns of $R(A,B)$ for independence in the order in which they appear in $R(A,B)$. This yields the following so-called Brunovskii–Luenberger canonical form or block companion canonical form for a completely-controllable pair $(A,B)$:

$$\bar{A}=S^{-1}AS=\Vert \begin{array}{ccc}\bar{A}{}_{11}& \dots & \bar{A}{}_{1m}\\ \cdot & & \cdot \\ \cdot & & \cdot \\ \cdot & & \cdot \\ \bar{A}{}_{m1}& \dots & \bar{A}{}_{mm}\end{array}\Vert ,$$

$$\bar{B}=S^{-1}B=(\bar{b}{}_1\dots \bar{b}{}_m),$$

where $\bar{A}{}_{ij}$ is a matrix of size $d_i\times d_j$ for certain $d_i\in \mathbf{N}\cup \{0\}$, $\sum _{i=1}^m{d}_i=n$, of the form

$$\bar{A}{}_{ii}=\Vert \begin{array}{ccccccc}0& 0& 0& \dots & 0& 0& \ast \\ 1& 0& 0& \dots & 0& 0& \ast \\ 0& 1& 0& \dots & 0& 0& \ast \\ \cdot & \cdot & \cdot & & \cdot & \cdot & \cdot \\ 0& 0& 0& \dots & 0& 1& \ast \end{array}\Vert ,$$

$$\bar{A}{}_{ij}=\Vert \begin{array}{cccc}0& \dots & 0& \ast \\ 0& \dots & 0& \ast \\ \cdot & & \cdot & \cdot \\ 0& \dots & 0& \ast \end{array}\Vert \text{ for }i\ne j,$$

and $\bar{b}{}_j$ for $d_j\ne 0$ is the $(d_1+\cdots +d_{j-1}+1)$- th standard basis vector of ${\mathbf{R}}^n$; the $\bar{b}{}_j$ with $d_j=0$ have arbitrary coefficients $\ast$. Here the $\ast$' s denote coefficients which can take any value. If $d_j$ or $d_i$ is zero, the block $A_{ij}$ is empty (does not occur). Instead of $\mathbf{R}$ any field can be used. The $d_j$ are called controllability indices or Kronecker indices. They are invariants.

Canonical forms are often used in (numerical) computations. This must be done with caution, because they may not depend continuously on the parameters [a3]. For example, the Jordan canonical form is not continuous; an example of this is:

$$\Vert \begin{array}{cc}1& t\\ 0& 1\end{array}\Vert \mapsto \Vert \begin{array}{cc}1& 1\\ 0& 1\end{array}\Vert \text{ for }t\ne 0,$$

$$\Vert \begin{array}{cc}1& 0\\ 0& 1\end{array}\Vert \mapsto \Vert \begin{array}{cc}1& 0\\ 0& 1\end{array}\Vert .$$

The matter of continuous canonical forms has much to do with moduli problems (cf. Moduli theory). Related is the matter of canonical forms for families of objects, e.g. canonical forms for holomorphic families of matrices under similarity [a4]. For a survey of moduli-type questions in linear control theory cf. [a5].

In the case of a controllable pair $(A,B)$ with $m=1$, i.e. $B$ is a vector $b\in {\mathbf{R}}^n$, the matrix $A$ is cyclic, see also the section below on normal forms for operators. In this special case there is just one block $\bar{A}{}_{11}$( and one vector $\bar{b}{}_1$). This canonical form for a cyclic matrix with a cyclic vector is also called the Frobenius canonical form or the companion canonical form.

References[edit]

Self-adjoint operator on a Hilbert space[edit]

A normal form of an operator is a representation, up to an isomorphism, of a self-adjoint operator $A$ acting on a Hilbert space $\mathcal{H}$ as an orthogonal sum of multiplication operators by the independent variable.

To begin with, suppose that $A$ is a cyclic operator; this means that there is an element $h_0\in \mathcal{H}$ such that every element $h\in \mathcal{H}$ has a unique representation in the form $F(A)h_0$, where $F(\xi )$ is a function for which

$$\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\int }}|F(\xi ){|}^{2}d(E_{\xi }{h}_0,h_0)<\mathrm{\infty };$$

here $E_{\xi }$, $-\mathrm{\infty }<\xi <\mathrm{\infty }$, is the spectral resolution of $A$. Let ${\mathcal{L}}_{\rho }^2$ be the space of square-integrable functions on $(-\mathrm{\infty },+\mathrm{\infty })$ with weight $\rho (\xi )=(E_{\xi }{h}_0,h_0)$, and let $K_{\rho }F=\xi F(\xi )$ be the multiplication operator by the independent variable, with domain of definition

$$D_{K_{\rho }}=\{F(\xi ):\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\int }}{\xi }^2|F(\xi ){|}^{2}d\rho (\xi )<\mathrm{\infty }\}.$$

Then the operators $A$ and $K_{\rho }$ are isomorphic, $A\simeq K_{\rho }$; that is, there exists an isomorphic and isometric mapping $U:\mathcal{H}\to {\mathcal{L}}_{\rho }^2$ such that $U{D}_A=D_{K_{\rho }}$ and $A=U^{-1}{K}_{\rho }U$.

Suppose, next, that $A$ is an arbitrary self-adjoint operator. Then $\mathcal{H}$ can be split into an orthogonal sum of subspaces ${\mathcal{H}}_{\alpha }$ on each of which $A$ induces a cyclic operator $A_{\alpha }$, so that $H=\sum \oplus H_{\alpha }$, $A=\sum \oplus A_{\alpha }$ and $A_{\alpha }\simeq K_{{\rho }_{\alpha }}$. If the operator $K=\sum \oplus K_{{\rho }_{\alpha }}$ is given on ${\mathcal{L}}^2=\sum \oplus {\mathcal{L}}_{{\rho }_{\alpha }}^2$, then $A\simeq K$.

The operator $K$ is called the normal form or canonical representation of $A$. The theorem on the canonical representation extends to the case of arbitrary normal operators (cf. Normal operator).

References[edit]

V.I. Sobolev

The normal form of an operator $A$ is a representation of $A$, acting on a Fock space constructed over a certain space $L_2(M,\sigma )$, where $(M,\sigma )$ is a measure space, in the form of a sum

$$\begin{array}{}\text{(1)}& A=\sum _{m,n\ge 0}\int K_{n,m}(x_1\dots x_n;y_1\dots y_m)\times \end{array}$$

$$\times a^{\ast }(x_1)\dots a^{\ast }(x_n)a(y_1)\dots a(y_m)\prod _{i=1}^{n}d\sigma (x_i)\prod _{j=1}^{m}d\sigma (y_j),$$

where $a(x),a^{\ast }(x)$( $x\in M$) are operator-valued generalized functions generating families of annihilation operators $\{a(f):f\in L_2(M,\sigma )\}$ and creation operators $\{a^{\ast }(f):f\in L_2(M,\sigma )\}$:

$$a(f)=\underset{M}{\int }a(x)f(x)d\sigma (x),a^{\ast }(f)=\underset{M}{\int }{a}^{\ast }(x)\bar{f}(x)d\sigma (x).$$

In each term of expression (1) all factors $a(y_j)$, $j=1\dots m$, stand to the right of all factors $a^{\ast }(x_i)$, $i=1\dots n$, and the (possibly generalized) functions $K_{n,m}(x_1\dots x_n;y_1\dots y_m)$ in the two sets of variables $(x_1\dots x_n)\in M^n$, $(y_1\dots y_m)\in M^m$, $n,m=0,1\dots$ are, in the case of a symmetric (Boson) Fock space, symmetric in the variables of each set separately, and, in the case of an anti-symmetric (Fermion) Fock space, anti-symmetric in these variables.

For any bounded operator $A$ the normal form exists and is unique.

The representation (1) can be rewritten in a form containing the annihilation and creation operators directly:

$$\begin{array}{}\text{(2)}& A=\end{array}$$

$$=\sum _{m,n}\sum _{\begin{array}{c}\{i_1\dots i_n\}\\ \{j_1\dots j_m\}\end{array}}{c}_{i_1\dots i_n{j}_1\dots j_m}{a}^{\ast }(f_{i_1})\dots a^{\ast }(f_{i_n})a(f_{j_1})\dots a(f_{j_m}),$$

where $\{f_i:i=1,2,\dots \}$ is an orthonormal basis in $L_2(M,\sigma )$ and the summation in (2) is over all pairs of finite collections $\{f_{i_1}\dots f_{i_n}\}$, $\{f_{j_1}\dots f_{j_m}\}$ of elements of this basis.

In the case of an arbitrary (separable) Hilbert space $H$ the normal form of an operator $A$ acting on the Fock space $\mathrm{\Gamma }(H)$ constructed over $H$ is determined for a fixed basis $\{f_i:i=1,2,\dots \}$ in $H$ by means of the expression (2), where $a(f)$, $a^{\ast }(f)$, $f\in H$, are families of annihilation and creation operators acting on $\mathrm{\Gamma }(H)$.

References[edit]

R.A. Minlos

Comments[edit]

References[edit]

Recursive functions[edit]

The normal form of a recursive function is a method for specifying an $n$- place recursive function $\varphi$ in the form

$$\begin{array}{}\text{(*)}& \varphi (x_1\dots x_n)=g(\mu z(f(x_1\dots x_n,z)=0)),\end{array}$$

where $f$ is an $(n+1)$- place primitive recursive function, $g$ is a $1$- place primitive recursive function and $\mu z(f(x_1\dots x_n,z)=0)$ is the result of applying the least-number operator to $f$. Kleene's normal form theorem asserts that there is a primitive recursive function $g$ such that every recursive function $\varphi$ can be represented in the form (*) with a suitable function $f$ depending on $\varphi$; that is,

$$(\mathrm{\exists }g)(\mathrm{\forall }\varphi )(\mathrm{\exists }f)(\mathrm{\forall }{x}_1\dots x_n):$$

$$[\varphi (x_1\dots x_n)=g(\mu z(f(x_1\dots x_n,z)=0))].$$

The normal form theorem is one of the most important results in the theory of recursive functions.

A.A. Markov [2] obtained a characterization of those functions $g$ that can be used in the normal form theorem for the representation (*). A function $g$ can be used as function whose existence is asserted in the normal form theorem if and only if the equation $g(x)=n$ has infinitely many solutions for each $n$. Such functions are called functions of great range.

References[edit]

V.E. Plisko

Comments[edit]

References[edit]

Normal form of a system of differential equations[edit]

A normal form of a system of differential equations

$$\begin{array}{}\text{(1)}& {\dot{x}}_i={\varphi }_i(x_1\dots x_n),i=1\dots n,\end{array}$$

near an invariant manifold $M$ is a formal system

$$\begin{array}{}\text{(2)}& {\dot{y}}_i={\psi }_i(x_1\dots y_n),i=1\dots n,\end{array}$$

that is obtained from (1) by an invertible formal change of coordinates

$$\begin{array}{}\text{(3)}& x_i={\xi }_i(y_i\dots y_n),i=1\dots n,\end{array}$$

in which the Taylor–Fourier series ${\psi }_i$ contain only resonance terms. In a particular case, normal forms occurred first in the dissertation of H. Poincaré (see [1]). By means of a normal form (2) some systems (1) can be integrated, and many can be investigated for stability and can be integrated approximately; for systems (1) a search has been made for periodic solutions and families of conditionally periodic solutions, and their bifurcation has been studied.

Normal forms in a neighbourhood of a fixed point.[edit]

Suppose that $M$ contains a fixed point $X\equiv (x_1\dots x_n)=0$ of the system (1) (that is, ${\varphi }_i(0)=0$), that the ${\varphi }_i$ are analytic at it and that ${\lambda }_1\dots {\lambda }_n$ are the eigen values of the matrix $\Vert \partial {\varphi }_i/\partial x_j\Vert$ for $X=0$. Let $\mathrm{\Lambda }\equiv ({\lambda }_1\dots {\lambda }_n)\ne 0$. Then in a full neighbourhood of $X=0$ the system (1) has the following normal form (2): the matrix $\Vert \partial {\psi }_i/\partial y_j\Vert$ has for $Y\equiv (y_1\dots y_n)=0$ a normal form (for example, the Jordan normal form) and the Taylor series

$$\begin{array}{}\text{(4)}& {\psi }_i=y_i\sum _{Q\in N_i}{g}_{iQ}{Y}^Q,i=1\dots n,\end{array}$$

contain only resonance terms for which

$$\begin{array}{}\text{(5)}& (Q,\mathrm{\Lambda })\equiv q_1{\lambda }_1+\cdots +q_n{\lambda }_n=0.\end{array}$$

Here $Q\equiv (q_1\dots q_n)$, $Y^Q\equiv y_1^{q_1}\dots y_n^{q_n}$, $N_i=\{Q:\text{ integers }{q}_j\ge 0,q_i\ge -1,q_1+\cdots +q_n\ge 0\}$. If equation (5) has no solutions $Q\ne 0$ in $N=N_1\cup \cdots \cup N_n$, then the normal form (2) is linear:

$${\dot{y}}_i={\lambda }_i{y}_i,i=1\dots n.$$

Every system (1) with $\mathrm{\Lambda }\ne 0$ can be reduced in a neighbourhood of a fixed point to its normal form (2) by some formal transformation (3), where the ${\xi }_i$ are (possibly divergent) power series, ${\xi }_i(0)=0$ and $\det \Vert \partial {\xi }_i/\partial y_j\Vert \ne 0$ for $Y=0$.

Generally speaking, the normalizing transformation (3) and the normal form (2) (that is, the coefficients $g_{iQ}$ in (4)) are not uniquely determined by the original system (1). A normal form (2) preserves many properties of the system (1), such as being real, symmetric, Hamiltonian, etc. (see , [3]). If the original system contains small parameters, one can include them among the coordinates $x_j$, and then ${\dot{x}}_j=0$. Such coordinates do not change under a normalizing transformation (see [3]).

If $k$ is the number of linearly independent solutions $Q\in N$ of equation (5), then by means of a transformation

$$y_i=z_1^{{\alpha }_{i1}}\dots z_n^{{\alpha }_{in}},i=1\dots n,$$

where the ${\alpha }_{ij}$ are integers and $\det \Vert {\alpha }_{ij}\Vert =\pm 1$, the normal form (2) is carried to a system

$${\dot{z}}_j=z_{i}f(z_1\dots z_k),i=1\dots n$$

(see , [3]). The solution of this system reduces to a solution of the subsystem of the first $k$ equations and to $n-k$ quadratures. The subsystem has to be investigated in the neighbourhood of the multiple singular point $z_1=\cdots =z_k=0$, because the $f_1\dots f_k$ do not contain linear terms. This can be done by a local method (see [3]).

The following problem has been examined (see ): Under what conditions on the normal form (2) does the normalizing transformation of an analytic system (1) converge (be analytic)? Let

$${\omega }_k=min|(Q,\mathrm{\Lambda })|$$

for those $Q\in N$ for which

$$(Q,\mathrm{\Lambda })\ne 0,q_1+\cdots +q_n<2^k.$$

Condition $\omega$: $\sum _{k=1}^{\mathrm{\infty }}{2}^{-k}\log {\omega }_k^{-1}<\mathrm{\infty }$.

Condition $\bar{\omega }$: $limsup{2}^{-k}\log {\omega }_k^{-1}<\mathrm{\infty }$ as $k\to \mathrm{\infty }$.

Condition $\bar{\omega }$ is weaker than $\omega$. Both are satisfied for almost-all $\mathrm{\Lambda }$( relative to Lebesgue measure) and are very weak arithmetic restrictions on $\mathrm{\Lambda }$.

In case $\mathrm{Re}\mathrm{\Lambda }=0$ there is also condition $A$( for the general case, see in ): There exists a power series $a(Y)$ such that in (4), ${\varphi }_i={\lambda }_i{y}_{i}a$, $i=1\dots n$.

If for an analytic system (1) $\mathrm{\Lambda }$ satisfies condition $\omega$ and the normal form (2) satisfies condition $A$, then there exists an analytic transformation of (1) to a certain normal form. If (2) is obtained from an analytic system and fails to satisfy either condition $\bar{\omega }$ or condition $A$, then there exists an analytic system (1) that has (2) as its normal form, and every transformation to a normal form diverges (is not analytic).

Thus, the problem raised above is solved for all normal forms except those for which $\mathrm{\Lambda }$ satisfies condition $\omega$, but not $\bar{\omega }$, while the remaining coefficients of the normal form satisfy condition $A$. The latter is a very rigid restriction on the coefficients of a normal form, and for large $n$ it holds, generally speaking, only in degenerate cases. That is, the basic reason for divergence of a transformation to normal form is not small denominators, but degeneracy of the normal form.

But even in cases of divergence of the normalizing transformation (3) with respect to (2), one can study properties of the solutions of the system (1). For example, a real system (1) has a smooth transformation to the normal form (2) even when it is not analytic. The majority of results on smooth normalization have been obtained under the condition that all $\mathrm{Re}{\lambda }_j\ne 0$. Under this condition, with the help of a change $X\to V$ of finite smoothness class, a system (1) can be brought to a truncated normal form

$$\begin{array}{}\text{(6)}& {\dot{v}}_i={\tilde{\psi }}_i(V),i=1\dots n,\end{array}$$

where the ${\tilde{\psi }}_i$ are polynomials of degree $m$( see [4]–). If in the normalizing transformation (3) all terms of degree higher than $m$ are discarded, the result is a transformation

$$\begin{array}{}\text{(7)}& x_i={\tilde{\xi }}_i(U),i=1\dots n\end{array}$$

(the ${\tilde{\xi }}_i$ are polynomials), that takes (1) to the form

$$\begin{array}{}\text{(8)}& {\dot{u}}_i={\tilde{\psi }}_i(U)+{\tilde{\varphi }}_i(U),i=1\dots n,\end{array}$$

where the ${\tilde{\psi }}_i$ are polynomials containing only resonance terms and the ${\tilde{\psi }}_i$ are convergent power series containing only terms of degree higher than $m$. Solutions of the truncated normal form (6) are approximations for solutions of (8) and, after the transformation (7), give approximations of solutions of the original system (1). In many cases one succeeds in constructing for (6) a Lyapunov function (or Chetaev function) $f(V)$ such that

$$|f(V)|\le c_1|V{|}^{\gamma }\text{ and }\left|\sum _{j=1}^n\frac{\partial f}{\partial v_j}{\tilde{\varphi }}_j\right|>c_2|V{|}^{\gamma +m},$$

where $c_1$ and $c_2$ are positive constants. Then $f(U)$ is a Lyapunov (Chetaev) function for the system (8); that is, the point $X=0$ is stable (unstable). For example, if all $\mathrm{Re}{\lambda }_i<0$, one can take $m=1$, $f=\sum _{i=1}^n{v}_i^2$ and obtain Lyapunov's theorem on stability under linear approximation (see [7]; for other examples see the survey [8]).

From the normal form (2) one can find invariant analytic sets of the system (1). In what follows it is assumed for simplicity of exposition that $\mathrm{Re}\mathrm{\Lambda }=0$. From the normal form (2) one extracts the formal set

$$\mathcal{A}=\{Y:{\psi }_i={\lambda }_i{y}_{i}a,i=1\dots n\},$$

where $a$ is a free parameter. Condition $A$ is satisfied on the set $\mathcal{A}$. Let $X$ be the union of subspaces of the form $\{Y:y_i=0,i=i_1\dots i_l\}$ such that the corresponding eigen values ${\lambda }_j$, $j\ne i_1\dots i_l$, $1\le j\le n$, are pairwise commensurable. The formal set $\mathcal{A}tilde=\mathcal{A}\cap K$ is analytic in the system (1). From $\mathcal{A}$ one selects the subset $\mathcal{B}$ that is analytic in (1) if condition $\omega$ holds (see [3]). On the sets $\mathcal{A}tilde$ and $\mathcal{B}$ lie periodic solutions and families of conditionally-periodic solutions of (1). By considering the sets $\mathcal{A}tilde$ and $\mathcal{B}$ in systems with small parameters, one can study all analytic perturbations and bifurcations of such solutions (see [9]).

Generalizations.[edit]

If a system (1) does not lead to a normal form (2) but to a system whose right-hand sides contain certain non-resonance terms, then the resulting simplification is less substantial, but can improve the quality of the transformation. Thus, the reduction to a "semi-normal form" is analytic under a weakened condition $A$( see ). Another version is a transformation that normalizes a system (1) only on certain submanifolds (for example, on certain coordinate subspaces; see ). A combination of these approaches makes it possible to prove for (1) the existence of invariant submanifolds and of solutions of specific form (see [9]).

Suppose that a system (1) is defined and analytic in a neighbourhood of an invariant manifold $M$ of dimension $k+l$ that is fibred into $l$- dimensional invariant tori. Then close to $M$ one can introduce local coordinates

$$S=(s_1\dots s_k),Y=(y_1\dots y_l),Z=(z_1\dots z_m),$$

$$k+l+m=n,$$

such that $Z=0$ on $M$, $y_j$ is of period $2\pi$, $S$ ranges over a certain domain $H$, and (1) takes the form

$$\begin{array}{}\text{(9)}& \begin{array}{c}\dot{S}={\mathrm{\Phi }}^{(1)}(S,Y,Z),\\ \dot{Y}=\mathrm{\Omega }(S,Y)+{\mathrm{\Phi }}^{(2)}(S,Y,Z),\\ \dot{Z}=(S,Y)Z+{\mathrm{\Phi }}^{(3)}(S,Y,Z),\end{array}\}\end{array}$$

where ${\mathrm{\Phi }}^{(j)}=O(|Z|)$, $j=1,2$, ${\mathrm{\Phi }}^{(3)}=O(|Z{|}^2)$ and $A$ is a matrix. If $\mathrm{\Omega }=\text{ const }$ and $A$ is triangular with constant main diagonal $\mathrm{\Lambda }({\lambda }_1\dots {\lambda }_n)$, then (under a weak restriction on the small denominators) there is a formal transformation of the local coordinates $S,Y,Z\to U,V,W$ that takes the system (9) to the normal form

$$\begin{array}{}\text{(10)}& \begin{array}{c}\dot{U}=\sum {\mathrm{\Psi }}_{PQ}^{(1)}(U)W^Q\exp i(P,V),\\ \dot{V}=\sum {\mathrm{\Psi }}_{PQ}^{(2)}(U)W^Q\exp i(P,V),\\ {\dot{w}}_j=w_j\sum g_{jPQ}(U)W^Q\exp (P,V),j=1\dots m,\end{array}\}\end{array}$$

where $P\in {\mathbf{Z}}^l$, $Q\in {\mathbf{N}}^m$, $U\in H$, and $i(P,\mathrm{\Omega })+(Q,\mathrm{\Lambda })=0$.

If among the coordinates $Z$ there is a small parameter, (9) can be averaged by the Krylov–Bogolyubov method of averaging (see [10]), and the averaged system is a normal form. More generally, perturbation theory can be regarded as a special case of the theory of normal forms, when one of the coordinates is a small parameter (see [11]).

Theorems on the convergence of a normalizing change, on the existence of analytic invariant sets, etc., carry over to the systems (9) and (10). Here the best studied case is when $M$ is a periodic solution, that is, $k=0$, $l=1$. In this case the theory of normal forms is in many respects identical with the case when $M$ is a fixed point. Poincaré suggested that one should consider a pointwise mapping of a normal section across the periods. In this context arose a theory of normal forms of pointwise mappings, which is parallel to the corresponding theory for systems (1). For other generalizations of normal forms see [3], , [12]–[14].

References[edit]

A.D. Bryuno

Comments[edit]

For more on various linearization theorems for ordinary differential equations and canonical form theorems for ordinary differential equations, as well as generalizations to the case of non-linear representations of nilpotent Lie algebras, cf. also Poincaré–Dulac theorem and Analytic theory of differential equations, and [a1].

References[edit]