Normal form of a matrix
The Singular Value Decomposition (SVD) of a matrix A is possibly the most powerful way of revealing the properties of this matrix.
The normal form (or "identity decomposition") of a matrix is another useful decomposition with a somewhat less ambitious goal : the only feature of A that we want to reveal is its rank (whereas SVD uncovers much more than that).
Let A be any matrix mxn of rank r.
We will show that there exist :
* Two square nonsingular matrices B(mxm) and C(nxn),
* And a "pseudo-identity" matrix H(mxn) whose off diagonal elements are 0s, but which is not square.
- The upper part of the diagonal (red strip in the illustration below) in H contains only 1s, and we'll show that their number is r, the rank of A.
- The lower part of the diagonal (gray strip) contains (n - r) 0s, just as the rest of H.
such that :
A = B-1HC -1 or, equivalently H = BAC
This decomposition may be represented as :
This figure illustrates the case r < n < m, but the decomposition is also valid for m n, and for r = min(m, n) (that is when A is full rank).
Despite the formal similarity with SVD, the normal form reveals less information about the matrix than SVD, as :
* Only the rank of A is read off the normal form,
* The matrices B and C are definitely not unique, and contain no straightforwardly usable information about A.
On the other hand, the normal form is easier to elaborate than SVD. We'll show that B and C can be obtained from A by resorting only to so-called elementary transformations that come in three kinds :
* (R1) Interchange of two rows.
* (R2 ) Multiplication of a row by a (non zero) number.
* (R3 ) Addition of the result of (R2 ) to another row.
with a similar set of elementary transformations for columns.
These transformations can be represented by elementary transformation matrices that :
* Left-multiply A for row transformations, and
* Right-multiply A for column transformations.
Just as SVD has a "full" and a "reduced" version, we'll show that the "full" normal form described above is equivalent to the following "reduced" form :
* Any matrix A(mxn) of rank r can be factored into two full rank matrices F and G of rank r:
A = FG
* F has m rows and G has n columns, so their product is mxn.
* Both are r columns (resp. rows) thick. So now the rank of A reads as the "thickness" of F or of G.
In this Tutorial, we show how any matrix A can be factored into a normal form. H will be obtained by successively applying elementary transformations to A, progressively building B and C in the process. The only small difficulty will be to show that the number of 1s in the diagonal of H is equal to r, the rank of A.
The reduced form will also be obtained easily with the help of a simple and classical result in Linear Algebra that we demonstrate.
We give another demonstration of the existence of the reduced normal form in the course of demonstrating Cochran's Theorem.
NORMAL FORM OF A MATRIX
Elementary transformations are matrices
Type 1 : interchanging two rows
Type 2 : multiplying a row by a number
Type 3 : adding the multiple of a row to another row
Elementary transformations preserve the rank
The normal form of a matrix
Transforming the first row
Transforming the first column
The upper left element
Iterating on the main submatrix
Stopping the process
The normal form is not unique
Rank of A
Reduced normal form
F and G are full rank, which is r
Reduced normal form and reduced SVD
Related readings :
Want to contribute to this site ?