Linear Algebra

Selected theorems

and

Documentation of the Shareware Library

=== degrees of freedom ===

Let us count-up the degrees of freedom and the constraints of various matrices and see how they add up.

Matrix			deg of freedom	amt of constraints	total
Real:
	Symmetric		n (n + 1) / 2	n (n – 1) / 2	n^2
	Skew-symmetric		n (n – 1) / 2	n (n + 1) / 2	n^2
	Ortho-normal		n (n – 1) / 2	n (n + 1) / 2	n^2
Complex:
	Hermitian		n^2	n^2	2 n^2
		Real-part	n (n + 1) / 2	n (n – 1) / 2	n^2
		Imaginary part	n (n – 1) / 2	n (n + 1) / 2	n^2
	Skew-Hermitian		n^2	n^2	2 n^2
		Real-part	n (n – 1) / 2	n (n + 1) / 2	n^2
		Imaginary part	n (n + 1) / 2	n (n – 1) / 2	n^2
	Unitary		n^2	n^2	2 n^2
		Real-part	n (n – 1) / 2	n (n + 1) / 2	n^2
		Imaginary part	n (n + 1) / 2	n (n – 1) / 2	n^2
		The ideal	n	---	---
		Its residue class	n (n – 1)	n	n^2

The values for the symmetric and those for the skew-symmetric are complementary. Their derivations are obvious. The amount of degrees of freedom for the ortho-normal matrix are inherited from those of the skew-symmetric matrix, by the bilinear theorems. The ortho-normal matrix is constrained by n normality requirements and by n (n – 1) / 2 – the combinations of n things, taken two at a time – by the orthogonality requirements. Again, the values for the Hermitian and the skew-Hermitian matrices are obvious. Since the real-part of an unitary matrix is an ortho-normal matrix, the values carry down from those of an ortho-normal matrix. As in the real case, the amount of degrees of freedom and the constraints for a unitary matrix are inherited from a skew-Hermitian matrix, by the bilinear theorems.

Now, let us see how the degrees of freedom add up for the several factorizations of matrices. The LDU inversion algorithm has the three factors: L and U each have the same amount of degrees of freedom as a skew-symmetric matrix, namely n (n – 1) / 2. The diagonal matrix D obviously has n degrees of freedom. The total is n^2. Checks. The factorization of a symmetric matrix S into the ortho-normal matrix O and the eigen-value matrix (another diagonal matrix) E has only two independent factors, namely S = O E Otr. The degrees of freedom for the ortho-normal matrix is n (n – 1) / 2, while those for the E matrix is n. The total is n (n + 1) / 2, which is equal to that of a symmetric matrix. Checks. The factorization of a real matrix A into the bra < (an ortho-normal matrix), diagonal D, and ket > (another ortho-normal matrix) has three factors, namely A = < D >. The degrees of freedom are, respectively, n (n – 1) / 2, n, and n (n – 1) / 2. The total is n^2, which is equal to that of a real matrix. Checks.

However, the values do not add up for the factorization of a Hermitian or a complex matrix. The factorization H = U E Utr has n^2 degrees of freedom on the left side. On the right side, the U has n^2 degrees of freedom and the E has n degrees of freedom, for a total of n (n + 1). This is an excess of n degrees of freedom. Hence, the unitary matrix is not unique. Indeed, we see that the residue class provides us with the requisite amount of degrees of freedom. So, how does it add up? The Hermitian matrix factors as Her = ResCl E ResCltr. The left-had side has n^2 degrees of freedom. The right hand side has only two independent factors: The residue-class has n (n - 1) degrees of freedom, while the eigenvalues factor has n degrees of freedom, for a total of n^2. Checks. The factorization of a complex matrix A into the bra <, diagonal D, and Ket > has three factors, namely A = < D > = ResCl D U. The degrees of freedom are, respectively n (n - 1), n, and n^2. The total is 2 n^2, which is equal to that of a complex matrix. Checks. Observe that the ket has more degrees of freedom than the bra.

Each eigenvector is an axial-vector – it may be multiplied by an arbitrary z of unit magnitude. This scalar multiplication is equivalent to an elementary rotation that would kill the corresponding element upon the imaginary diagonal. These n elementary rotations constitute the ideal. Actually, since any Hermitian matrix has zeros along its imaginary diagonal, the necessity to kill any of these elements never arises. Since we are concerned only with the multiplicative group of the ring of matrices, instead of the concept of an ideal of a ring, consider the easier concept of a normal subgroup.

The QR matrix inversion and the Cholesky matrix factorization algorithms. Each of the foregoing algorithms was constructed for a specific pre-defined purpose. Then, a proof was devised to establish the validity of the resulting production and its conformance to the intended purpose. The balance of the degrees of freedom served as a further check upon the validity of each of those algorithms.

On the other hand, each of the current two algorithms was constructed first; then, the resulting production was analyzed. Hence, the balance of the degrees of freedom of the production is a foregoing conclusion. However, the balance of the degrees of freedom of the description of the production serves to validate this description. Thus, we proceed with the accounting of the degrees of freedom.

As a preliminary, we observe that the right-triangular matrix may be regarded as a product of a diagonal matrix and an upper-triangular matrix. Hence, the degrees of freedom of the right-triangular matrix is the sum of those of the diagonal matrix and the upper-triangular matrix. Likewise, the degrees of freedom of the left-triangular matrix is the sum of those of the diagonal matrix and the lower-triangular matrix.

We observe that in the Cholesky factorization of a matrix A as A = O R Otr, since the Otr is dependent upon the O, only the degrees of freedom of the O and the R matrices count towards the total on the right-hand side. Hence, we may combine the discussion of the Cholesky factorization with that of the QR factorization, which is A = O R.

For a real matrix A, the QR matrix inversion performs the factorization A = O R, where O is an orth-normal matrix and R is a right-triangular matrix. From the foregoing table, the matrix O has n (n - 1) / 2 degrees of freedom. As we said, the right-triangular matrix R may be considered to be a product of a diagonal matrix -- which has n degreees of freedom -- and an upper-triangular matrix -- which has n (n - 1) / 2 degrees of freedom. The sum is n, which checks with the degrees of freedom of the real matrix A. For a complex matrix A, per the foregoing discussion of the residue class, the unitary matrix O has a net of n (n - 1) degrees of freedom. For any complex matrix input into the Jacobi algorithm, the Jacobi algorithm -- and hence the Cholesky algorithm as well -- does not attempt to kill the purely-imaginary diagonal. Hence, the complex diagonal matrix has 2 n degrees of freedom. The complex upper-triangular matrix has n (n - 1) degrees of freedom. The sum is 2 n, which checks with the degrees of freedom of the complex matrix A.

Note: Depending upon the details of the implementation, the actual program for a Jacobi factorization will require minor modifications to serve as a Cholesky factorization of a general real (or general complex) matrix.

UP NEXT