Gauss-Lagrange Algorithm for Real Quadratic Forms

Suggested Installation

Create a directory called [...]/AddOns/ExtraPackages/LinearAlgebra if it does not already exists, where [...] stands for your main Mathematica directory. Copy the file GaussLagrange.m in that directory. Then you can load the package with the following line :

<< LinearAlgebra`GaussLagrange`

If you choose to store the file elsewhere, you can still load it with :

\(<< [path]\GaussLagrange.m\)

where [path] stands for the path of the directory in which you have put the file.

Elementary Row and Column Operations

This package implements elementary row and column operations on any matrix. I know this has probably been done elsewhere, but I included these so the package does not need to call any external function.

R[{i, j}, m]			Swaps rows i and j of matrix m
	R[i, c, m]			Multiplies row i of m by c
	R[i, j, c, m]			Adds c times row j to row i of m
	Col[{i, j}, m]		Swaps columns i and j of m
	Col[i, c, m]			Multiplies column i of m by c
	Col[i, j, c, m]		Adds c times column j to column i of m

The following examples are quite self-explanatory.

m = {{a, b}, {c, d}}

R[{1, 2}, m]

Col[2, 3, m]

R[2, 1, 2, m]

Associated Matrix of a Quadratic Form

A real quadratic form is an homogenous polynomial of degree 2 in one or several variables. Any expression of the form v.m.v, where v is a n-vector of variables and m a n×n real matrix, is a quadratic form, such as the following :

\(v = {x, y, z}; 
	
    m = {{1, 2, 3}, {\(-2\), 3, \(-1\)}, {2, \(-1\), 0}}\ ; 
	
    Expand[v.m.v]\)

For any quadratic form q in vector of variables v, the matrix associated with the form is the n×n real symmetric matrix m such that v.m.v == q.

AssociatedMatrix[q, x]	The associated matrix of the quadratic form q in
						vector of variables x

AssociatedMatrix[
      (α^2) + (β^2) - 2  α β, {α, β}]

AssociatedMatrix[
      4  x y - 5  x z + 2  (y^2) - 4  y z + 2  (z^2), {x, y, z}]

We can check that we get the quadratic form back from the matrix :

{x, y, z}.%.{x, y, z}  //  Expand

Gauss-Lagrange Algorithm

If a and b are two square matrices of the same dimension, then they are said to be congruent if there exists an invertible matrix p such that p.a.Transpose[p] == b. Congruence, defined that way, is an equivalence relation on the set of square matrices of the same dimension which preserves symmetry. So, given any symmetric matrix m, we will want to find the simplest possible matrix d to which m is congruent. This is what the so-called Gauss-Lagrange algorithm achieves.

GaussLagrange[m]		Returns {d, p}, where d is the canonical 
						form of m under congruence, and p is such that 
						p.d.Transpose[p] == m.

Here we apply the algorithm to a simple 3×3 matrix :

m = {{1, -2, 3}, {-2, 6, -10}, {3, -10, 8}}

{d, p} = GaussLagrange[m]

Now we check we get the expected result :

p.m.Transpose[p]  ==  d

Here is another example :

m = {{2, 4, 6, 4}, {4, 5, 9, -4}, {6, 9, 19, -8}, {4, -4, 
          -8, -24}}

{d, p} = GaussLagrange[m]

p.m.Transpose[p] == d

Properties of Quadratic Forms

Given a quadratic form q in x, we define four properties which we can easily read from the canonical form under congruence of its associated matrix, namely :

- order : 	number of variables;
	- rank : 	number of elements ≠ 0 on the diagonal;
	- index : 	number of 1's on the diagonal;
	- signature :	 number of 1's minus number of -1's on the diagonal.

Thus, the following quadratic form q has order 3, rank 3, index 2 and signature 1.

\(q = 
      x\_1\^2 - 4 \( x\_1\) x\_2 + 2  x\_2\^2 + 6 \( x\_1\) x\_3 - 
        7  x\_3\^2; 
    
{d, p} = GaussLagrange[AssociatedMatrix[q, {x\_1, x\_2, x\_3}]]; 

    d\  // \ MatrixForm\)

Moreover, a quadratic form q in x can be :

- positive definite : 		q > 0 for all x ≠ 0;
	- positive semi-definite : 	q ≥ 0 for all x;
	- negative definite : 		q < 0 for all x ≠ 0;
	- negative semi-definite : 	q ≤ 0 for all x;
	- indefinite : 			q > 0 for some x, q < 0 for some other;
	- or identically 0 :		q ==  0 for all x.

The Summary function provides a convenient way to get all this information.

Summary[q,x]			Prints information about quadratic form q in x
	Summary[m]			Prints information about the quadratic form
						associated with symmetric matrix m

Thus, for the previous example, we get:

Summary[q, {(Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3])}]

Here is another example :

Summary[
      (x^2) + (y^2) - 2  x z + y z + 2  (z^2) - 6  x t + 4  y t + 2  z t + 
        26  (t^2), {x, y, z, t}]

Gabriel Chênevert
Student at Université de Montréal
Montréal, Québec, Canada
July 1999

Please feel free to e-mail me with any question, comment or suggestion at
cheneveg@jsp.umontreal.ca, or via http://www.jsp.umontreal.ca/~cheneveg.