New matrix factorization resembling Cholesky but more useful for integer matrices ==================Warren D. Smith=====Nov 2011=================== If S is a positive definite real symmetric matrix it can be "Cholesky factored" into S = L * L^T where L is lower triangular and the T denotes transpose. If S is positive definite complex Hermitian, there is an analogous factorization S = L * L^H where L is lower triangular and the H denotes Hermitian conjugate, i.e. complex-conjugate transpose. I want now to bring your attention to the idea of allowing the entries of S to be QUATERNIONS. Then S = L * L^H where L is lower triangular and the H denotes Hermitian conjugate, i.e. quaternionic-conjugate transpose. In all three cases, the entries of L can be computed row-by-row via left-to-right raster scan by Lab = (Sab - sum(0<k<b)of Lak Lbk') / Lbb when a>b and |Lbb| = sqrt( Sbb - sum(0<k<b)of Lbk Lbk' ) where the ' denotes conjugate, empty sums are 0, and in the square root, we always take the square root of a positive pure-real number. HOWEVER if we allow L's entries to be complex or quaternion, we can use for Lbb ANY complex or quaternion whose length |Lbb| is given by that square root. We do not need to make the diagonal entries of L always be pure-real and positive, although we could. Why are quaternions interesting? Because of Lagrange's "four-squares theorem." This tells us there is always an INTEGER quaternion Q with |Q|^2 = Q Q' = Q' Q equal to any desired nonnegative integer. Hence, there is always a matrix factorization of any INTEGER QUATERNIONIC-HERMITIAN matrix S, into L L^H where L is lower triangular with RATIONAL quaternion entries. This is superior to the complex and real versions of Cholesky, which by taking square roots generally goes outside the field of the rationals making exact arithmetic practically impossible. ==========An application=========== There are probably many applications of this observation. Let me focus on one: point-sets with distances that are square roots of integers. If Dab is the integer distance between points a and b in n-dimensional space then we might want to actually find coordinate vectors for points realizing those distances. One way to do that is this. Place one point at (0,0,0,...,0). Make the other n points be the n rows of lower triangular matrix L (which if it has quaternion entries, means the points will lie in 4n-dimensional space, but since there are only n+1 points they will really lie in an n-dimensional subspace of it). Then S = L L^H is an nXn hermitian matrix, and Saa = D0a^2 are the diagonal entries and the off-diagonal entries are Sab = (D0a^2 + D0b^2 - Dab^2)/2. Thus S is an nXn matrix whose entries are known half-integers. By quaternion-Cholesky factoring it, we get L giving coordinates in 4n-dimensional space which will instantiate any distances that are sqrt(integer)s that can be achieved in a Euclidean space... AND will do so with every coordinate rational. -- Warren D. Smith http://RangeVoting.org  <-- add your endorsement (by clicking "endorse" as 1st step)