Orthogonalization

The functions in this section perform orthogonalization and orthonormalization of lattice bases over the field of fractions of the base ring. Note that this yields a basis orthogonalization of the space in which a lattice embeds; in contrast OrthogonalDecomposition returns a decomposition into orthogonal components over the base ring. Basis orthogonalization is equivalent to diagonalization of the inner product matrix of a space.

Orthogonalize(M) : MtrxSpcElt -> MtrxSpcElt, AlgMatElt, RngIntElt

Given a basis matrix M over a subring R of the real field, compute a matrix N which is row-equivalent over to M over the field of fractions K of R, but whose rows are orthogonal (i.e., NN^tr is a diagonal matrix). This function returns three values:

(a)

An orthogonalized matrix N in row-equivalent to X over K;

(b)

An invertible matrix T in the matrix ring over K whose degree is the number of rows of M such that TM = N;

(c)

The rank of M.

Orthogonalization(F) : MtrxSpcElt -> MtrxSpcElt, AlgMatElt, RngIntElt

OrthogonalizeGram(F) : MtrxSpcElt -> MtrxSpcElt, AlgMatElt, RngIntElt

Given a symmetric n x n matrix F over R, where R is a subring of the real field, compute a diagonal matrix G such that G=TFT^tr for some invertible matrix T over K, where K is the field of fractions of R. F need not have rank n. This function returns three values:

(a)

A diagonal matrix G defined over R;

(b)

An invertible n x n matrix T over K such that G=TFT^tr;

(c)

The rank of F.

OrthogonalizeGram(F, a) : MtrxSpcElt, FldAut -> MtrxSpcElt, AlgMatElt, RngIntElt

Given an n x n matrix F over a field K of characteristic not 2, which is Hermitian with respect to the automorphism a, compute a diagonal matrix G such that G=TFa(T^tr) for some invertible matrix T over K. F need not have rank n. This function returns three values:

(a)

A diagonal matrix G defined over K;

(b)

An invertible n x n matrix T over K such that G=TFa(T^tr);

(c)

The rank of F.

Orthogonalize(L) : Lat -> Lat, AlgMatElt

For a lattice L, return a new lattice having the same Gram matrix as L but embedded in an ambient space with diagonal inner product matrix.

Orthonormalize(M, K) : MtrxSpcElt, Fld -> AlgMatElt

Cholesky(M, K) : MtrxSpcElt, Fld -> AlgMatElt

Orthonormalize(M) : MtrxSpcElt -> AlgMatElt

Cholesky(M) : MtrxSpcElt -> AlgMatElt

For a symmetric, positive definite matrix M, and a real field K, return a lower triangular matrix T over K such that M = TT^tr. The algorithm must take square roots so the result is returned as a matrix over the real field K. If the real field K is omitted, K is taken to be the default real field. Note that this function takes a Gram matrix M, not a basis matrix as in the previous functions.

Orthonormalize(L, K) : Lat, FldRe -> AlgMatElt

Cholesky(L, K) : Lat, FldRe -> AlgMatElt

Orthonormalize(L) : Lat -> AlgMatElt

Cholesky(L) : Lat -> AlgMatElt

Given a lattice L with Gram matrix F, together with a real field K, return a new lattice over K which has the same Gram matrix F as L but has the standard Euclidean inner product. (This will involve taking square roots so that is why the result must be over a real field.) The argument for the real field K may be omitted, in which case K is taken to be the current default real field. This function is equivalent to the invocation LatticeWithBasis(Orthonormalize(GramMatrix(L), K)). It is sometimes more convenient to work with the resulting lattice since it has the standard Euclidean inner product.

> L := Dual(CoordinateLattice(Lattice("Kappa", 12)));
> SL := ShortestVectors(L); 
> SL := SL cat [ -v : v in SL ]; #SL;
756
> time { (v,w) : v,w in SL };
{ -4, -2, -1, 0, 1, 2, 4 }
Time: 7.120
> M := Orthogonalize(L);
> SM := ShortestVectors(M);
> SM := SM cat [ -v : v in SM ]; #SM;
756
> time { (v,w) : v,w in SM };
{ -4, -2, -1, 0, 1, 2, 4 }
Time: 1.300