A quadratic form combines variables in a sum of terms, each of which multiplies together two of the variables or takes the square of one of them, and applies some scaling. (Similar expressions including simple multiples of just one variable aren't quadratic forms, but often can be re-arranged as one by adding a constant to the expression and replacing a relevant variable by the result of adding some constant to it.) The theory of quadratic forms revolves around finding suitable combinations of the variables for which the form can be put into simpler terms.
Quadratic forms are most usually encountered with real variables; when the variables range over the complex numbers, the hermitian form is generally more interesting, in which each term in the sum is a product of a variable with its conjugate or that of another, multiplied by some scaling, for which the form's values are always real. If a hermitian form's variables are restricted to the reals (which are self-conjugate), it is thus a simple quadratic form, as above.
Consequently, a quadratic form is simply a hermitian form restricted to
the reals, so I'll mainly discuss the more general hermitian form rather than
the quadratic; in support of the restriction to reals, I'll distinguish
between the reals (which arise as the values of the form) and
the scalar
values that our variables take – these are reals for a
quadratic form, but complex numbers in the hermitian case. All mentions of
conjugation can be read as fatuous in the real case, since
conjugation,
with i = √(−1), acts as the identity on {reals}. For the same reason, in the real case, there is no distinction between linear and conjugate-linear maps (both respect addition; a linear map respects scalings, while a conjugate-linear one conjugates scaling, which is the same as respecting it when conjugation is the identity). In one or two cases the reasoning for the two cases shall be slightly different (because I can use non-real scalings in the complex case, which both enables some methods of proof and requires proof of more things), obliging me to split the discussion, but mostly the analysis is the same.
A hermitian or quadratic form is described as positive
semi-definite
if its value is never negative, for any values of its
variables. Naturally, it can be zero, by setting all variables to zero; if,
aside from this case, its value is always positive, it's described
as positive definite. Likewise, a never-positive form is
called negative semi-definite
and one that's negative unless all
variables are zero is described as negative definite
. Negating a
negative-definite or negative semi-definite form necessarily gives the
positive equivalent, and conversely.
The norm of any complex number is just its product with its conjugate; in
the real case, this is just its square. The norm of zero is zero and that of
any other complex number is positive; so any sum of norms of linear combinations
of variables is a positive semi-definite form – and positive definite if
the original variables can all be recovered as linear combinations of the linear
combinations used in the sum of norms. When a form can be expressed as a sum,
each term of which is some simple scaling (necessarily real, as it happens)
times the norm of some linear combination of variables, the form is said to
be diagonal (in reference to the form of the matrix
representing the associated conjugate-linear map, below); finding the linear
combinations needed to express a form in this manner is known as diagonalising
it. When the scalings used by a diagonal form are all ±1 or 0, the form
is said to be unit-diagonalised
; in this case, it is simply the
difference between two sums of unscaled norms of linear combinations of the
original variables. I shall, below, show how to reduce
any hermitian or quadratic form to this unit-diagonal form.
If we make a list of the variables combined by the form, the possible values the variables can take lead to the list's values being members of the vector space V = {list ({scalars}: |n)}, where the natural n is the number of variables we have. Each term in our form is a scaling times a product of two variables, one of them conjugated. Let v be the vector of our variables; let u be a vector in the same space as v; in each term in our sum, replace the conjugated variable from v by the corresponding variable from u (for the plain quadratic form, chose either variable in each term to replace by its equivalent in u). The result can be construed as a function of u and v, g(u, v), whose value when u = v is our form; but we can now vary u and v separately.
Now, for fixed u, look at how g(u, v) varies with v: it is a sum of terms, each of which is some scalar (including a factor of a conjugated variable from u) times a co-ordinate of v; as such, it is a linear map from V; and its value is a scalar, so it's a linear map ({scalars}: |V) and, as such, a member of dual(V). Thus g(u) is in dual(V) and g is a mapping (dual(V): g |V). When our scalars are complex, it isn't linear, because scaling u by some constant k causes g(u) to be scaled by k's conjugate, *k. It does, however, do this consistently; and it respects addition, g(u+w) = g(u)+g(w); so it's a conjugate-linear map. Thus g is conjugate-linear (dual(V): |V) and (: g(v, v) ←v :V) is our quadratic form.
Each member w of dual(V) is a mapping ({scalars}: |V) so we can compose * after it to get *&on;w = ({scalars}: *(w·v) ←v |V) as a conjugate-linear mapping from V to scalars. Conversely, we can compose * after any conjugate-linear map from V to scalars; the result shall be a member of dual(V), so composing * after it gives us back our original conjugate-linear. Thus, in fact, every conjugate-linear ({scalars}: |V) is *&on;w for some w in dual(V). This, in turn, means we can represent any conjugate-linear map from V as a sum of tensor products of outputs of the map with composites of * after members of dual(V). In particular, g can be written as a sum of terms of form z×(*&on;w) with z and w in dual(V).
With complex scalars, our form is only hermitian if g(v, v) is always real; we must identify what constraint this imposes on g. Now, for any u and v in V, g(u+v, u+v) = g(u, u) +g(u, v) +g(v, u) +g(v, v), in which g(u+v, u+v), g(u, u) and g(v, v) are all real; hence g(u, v) +g(v, u) must be real, for every u, v in V. The same must also be true with i.u in place of u, so both g(v, u) +g(u, v) and i.(g(v, u) −g(u, v)) are real; from the former, g(v, u) and g(u, v) have opposite imaginary parts; from the latter, their real parts must be equal; hence we have g(u, v) = *(g(v, u)). So swapping the order of g's inputs conjugates the output.
As g is a function that takes two parameters, it has a transpose, which accepts the same two arguments in the reversed order, transpose(g, u, v) = g(v, u), which is scalar, so we can conjugate it; *&on;transpose(g, u) = (: *(g(v, u)) ←v |V). Now, as g is conjugate-linear, for fixed u, transpose(g, u) = (: g(v, u) ←v |V) is conjugate-linear, hence *&on;transpose(g, u) is linear ({scalars}: |V), i.e. in dual(V). For each v, (: g(v, u) ←u |V) is linear, so (dual(V): *&on;transpose(g, u) ←u |V) is conjugate-linear; thus it is of the same kind as g, an conjugate-linear map from V to its dual. So define
and notice that this is self-inverse and conjugate-linear. This gives hermite(g, u, v) = *(g(v, u)), for any conjugate-linear map g from a vector space to its dual. Our constraint above – to make g(v, v) always real by requiring g(u, v) = *(g(v, u)) for all u, v – can then be restated as g = hermite(g). This constraint is necessary for our form to be hermitian; furthermore, it is sufficient, as it makes each g(v, v) self-conjugate, i.e. real. Such a mapping, g = hermite(g), from a vector space to its dual is described as symmetric (or, equivalently, hermitian).
In the real case, our actual quadratic form is g(v, v) ←v, with v the
original vector of variables; as such, g(u, v) is not generally accessible,
although g(u+v,u+v) −g(u,u) −g(v,v) = g(u, v) +g(v, u) does give us
the value of g+hermite(g), with hermite in this case indistinguishable from
transpose. Writing s = (g +hermite(g))/2 and a = (g −hermite(g))/2, so
that g = s +a, we have s symmetric while a is antisymmetric, in
the sense hermite(a) = −a; every conjugate-linear (dual(V): |V) can be
written in this form, with s described as the symmetric part
of g and a
as its antisymmetric part
. As a is antisymmetric, so −a(u, v) =
*(a(v, u)) for all u, v, we get 0 = *(a(u, v)) +a(v, u) and, when u = v, half of
this is the real part of a(v, v), so a(v, v) is always imaginary. For real
variables and real coefficients, the only imaginary value available is 0, so
a(v, v) = 0 for all v, making g(v, v) = s(v, v) for all v. Thus we can use s in
place of g and restrict our attention to the case where g is symmetric, in the
real case just as in the complex case.
None the less, I'll also study the case of antisymmetric linear (dual(V): |V) in due course, since this can also be of interest; and it completes the underlying theory of linear maps (dual(V): |V), since every such mapping can be expressed as a sum its symmetric and antisymmetric parts, as noted above. Note that, in the complex case, an antisymmetric g, with hermite(g) = −hermite(g), is simply the result of scaling a symmetric one by an imaginary factor, since hermite is conjugate-linear, so hermite(i.g) = −i.hermite(g) = i.g. So the antisymmetric complex case reduces trivially to a simple transformation of the hermitian case (so that analysis of the symmetric case suffices for a full discussion of conjugate-linear (duall(V):|V), in the complex case, without need of a separate discussion of its antisymmetric case).
Our quadratic form is a sum of terms, each a product of two of the scalar variables we're treating as components of a vector in V; the number of potential terms in the sum grows as the square of the number of variables; we've reduced to roughly half that by restricting attention to either the symmetric case or the antisymmetric case. That implies a lot of (at least apparent) potential complexity. By rewriting the form in terms of linear combinations of the original variables, and dealing with these combinations as the interesting variables thereafter, we can transform one quadratic form into another; our aim shall be to find how simple a form we can transform to.
Replacing our original variables with linear combinations of them amounts to chosing a new basis of our linear space, V. Suppose, then, we have some given basis of V; e.g. the one that trivially arises from our initial conception of V's points as lists of values taken by our variables, with each basis member being a list in which one entry is a 1 and all others are 0; there is one such list for each position in our lists. Our basis is then (V:b|n) for some natural n, the dimension of V, and there is a dual basis (dual(V):p|n) for which p(k)·b(k) is 1 if h = k, otherwise 0.
Given a basis, b, we can permute its entries; we can scale any or all of its entries by any non-zero scaling; or we can add, to any of its members, a linear combination of the others; the resulting list shall also be a basis. The way to simplify quadratic forms is by repeated application of these steps, to turn whatever basis we start with into a basis with respect to which the form is simplified.
First consider the case where (dual(V): g |V) is symmetric (and scalars may be complex). Given a basis (V:b|n), suppose there is some m in n for which m in h in n implies, for each k in n, either k = h or g(b(h), b(k)) = 0. This trivially holds true for m = n−1 for our initial basis, as long as n > 0, as there is then no h in n with h > n−1.
We can thus reduce m to 0, at which point we have a basis b for which g(b(h),b(k)) = 0 for all h, k in n with h ≠ k; and each g(b(k),b(k)) is real. For those k for which g(b(k),b(k)) is non-zero, we can even replace b(k) by the result of dividing it by the square root of the absolute value of g(b(k),b(k)) to make each g(b(k),b(k)) be in {0, ±1}.
Let p be the dual of this basis, b. Each v in V is sum(: p(k,v).b(k) ←k |n), in which each p(k,v) is a scalar, so that
but g(b(h),b(k)) = 0 unless k = h, so
Each g(b(k),b(k)) is a real, so let s = ({reals}: g(b(k),b(k)) ←k |n) and we get g = sum(: s(k).p(k)×(*&on;p(k)) ←k |n). As a mild abuse of notation (a charge one can also lay against my use of conjugate-linear *&on;p(k) in a tensor product), I'll write *p = (: *&on;p(k) ←k |n) to simplify this to g = sum(s.p×*p). As noted above, we can arrange for each s(k) to be 0 or ±1.
Each p(k) corresponds to a linear combination of the variables we originally started with; so we have now reduced the terms making up our quadratic form to simple norms of such combinations, either positive or negative; we have unit-diagonalised our form. We can simply ignore the p(k) for which s(k) is zero, of course.
Any quadratic or hermitian form in n variables can thus be reduced (as I anticipated in the introduction) to one sum of norms of linear combinations of our original variables, minus another such sum. The number of terms in the two sums, taken together, is at most the number of variables we started with; so the number of meaningfully different forms in n variables is just (at most – I haven't yet shown that two forms with distinct numbers of positive and negative terms can't be equivalent under any change of basis) the number of ways of chosing q, m ≤ n with q+m ≤ n, with q the number of positive norms and m the number of negative ones; q can take any value from 0 to n and, given q, m can take any value from 0 to n+1−q, so we have sum(: 1+n−q ←q |1+n) = (1+n).(1+n) −n.(1+n)/2 = (1+n).(2+n)/2 meaningfully distinct forms in n variables. (Of these, we've effectively reduced all but 1+n to forms in fewer than n variables; and, if we treat forms as equivalent when each is simply some real multiple of the other, we can halve the number (rounding up if odd) of forms we actually distinguish.)
So we've reduced the collection of different hermitian forms in n variables from an n.(1+n)/2-dimensional space of possible symmetric conjugate-linear maps (dual(V): |V) to the (1+n).(2+n)/2 choices of pairs of naturals m, q ≤ n with m+q ≤n. The former is a collection with infinitely many values (indeed, an uncountable infinity of scalars, raised to a power that grows quadratically in n) while the latter is finite. That's quite a good simplifaction to achieve !
Note, in passing, that any g = sum(: s.p×*p :) with ({non-zero scalars}: s |n) and (dual(V): p |n) a basis is necessarily invertible: specifically, with (V: b |n) as the basis of V dual to p, g's inverse is f = sum(: b×*b/s |n). Since each s(k) is non-zero, it has a multiplicative inverse, so we can divided by it, as this requires. We get
but b(h)·p(k) is 1 when h is k, else zero;
each of which is the relevant identity. Any positive-definite or negative-definite form, when unit-diagonalised, necessarily has only +1 or −1 (respectively) as scalings (outputs of s), hence meets the requirement here and is invertible.
Now, Pythagoras's theorem leads to the lengths of displacements in a Euclidean space being expressible as the square roots of sums of squares of Cartesian coordinate differences on the space. Such coordinates amount to a choice of basis for which the squared length of a vector is the sum of the squares of the components of that vector with respect to the given basis. Thus the square of a vector's length is a hermitian form and (as we have q = n) it's positive definite. The above thus duly lets us express it as L = sum(: p×*p :) for some basis p of dual(V). Such a mapping, that mediates the notion of length in its space via the square root of the hermitian form it generates, is known as a metric on the linear space V on whose members it acts.
In a context which comes equipped with a metric, it is typically nice to be able to restrict one's bases to those for which the metric takes its canonical form, L = sum(: p×*p :) with p beint the basis of dual(V). The basis b of V dual to p then has L(b(k)) = sum(: p(h).(p(h)·b(k)) ← h :) with p(h)·b(k) being zero unless h = k, when it's 1, so L(b(k)) = p(k) and p = L&on;b is dual to b. This necessary condition is then sufficient to ensure our basis b has L(b(h),b(k)) equal to 1 when h = k and 0 otherwise; which is exactly what it takes to make L unit-diagonal with respect to b. We thus have a fixed positive-definite (hence invertible) form for whose associated conjugate-linear (dual(V): L |V) we want to restrict our choices of basis b to those for which L&on;b is dual to b; doing this ensures L remains unit-diagonalised.
In such a context, then, how nicely can we express the (dual(V): g |V) associated with some other hermitian form ? At first sight, it might appear that keeping L in its standard form would severely limit how much we can simplify g's representation.
Let's look again at the way we diagonalised g above, with a basis (V: b |n) and some m for which m in h in n implies g(b(h), b(k)) whenever h ≠ k in n. When g(b(k)) is zero, for some k < m, we can permute our basis as before to swap b(k) with b(m); this will preserve L&on;b dual to b. When g(b(m),b(m)) = 0 = g(b(k),b(k)) with non-zero z = g(b(k),b(m)), replacing b(m) with b(m) +z.b(k) would break L&on;b's duality to b; but replacing b(m) and b(k) by (b(m) +z.b(k))/√(1 +norm(z)) and (b(k) −(*z).b(m))/√(1 +norm(z)) won't.
The remaining case has g(b(k),b(k)) ≠ 0 (and necessarily real) for some k ≤ m. Previously, we changed each b(h) with m ≥h ≠ k by a suitable amount of b(k) to make g(b(h), b(k)) be zero; but this shall typically break L&on;b's duality to b. For each such h, we would need to also rescale b(h), after adding some b(k) to it; and make a matching change to b(k); but, then, each h's change to b(k) would complicate the changes from the others. In particular, if we first make some g(b(h),b(k) zero while keeping L&on;b dual to b, then move on to do the same for b(j) with m ≥ j ∉ {k, h}, the changes we make to b(j) and b(k) to make g(b(j),b(k)) = 0 while keeping L&on;b dual to b shall, if g(b(j),b(h)) is non-zero, make g(b(h),b(k)) non-zero.
One can, computationally, do reasonably well, despite this – always pick the k with largest g(b(k),b(k)) and, of the h with m ≥ h ≠ k, the one with largest g(b(k),b(h)); after reducing g(b(k),b(h)) to zero, subsequent elimination of g(b(k),b(j)) for j ≠ h shall make g(b(k),b(h)) non-zero but smaller than it or g(b(k),b(j)) was previously, so repeatedly doing this shall reduce the magnitudes of all off-diagonal values of g until, computationally, they're all negligible. It remains that we need a proof that there is a truly exact solution, in order to be sure such a procedure has a chance of converging.
So we need another approach: fortunately, one presents itself. We have positive-definite conjugate-linear (dual(V): L |V); it's non-singular, as noted above, and has an inverse, which is naturally conjugate-linear (V: |dual(V)); if we compose this after g, we get linear f = (V: L\g |V), for which L&on;f = L/L\g = g. As an endomorphism of V, f has a characteristic polynomial whose degree is the dimension of V; this necessarily has at least one root, yielding an eigenvalue of f with at least some eigenvector, so let's look at how L interacts with the eigenvectors of f = L\g, for given symmetric g.
First, for linear (V: f |V) and positive-definite symmetric conjugate-linear (dual(V): L |V) to give symmetric g = L&on;f, we require L&on;f = hermite(L&on;f), so let's look at what hermite does to a composite. For that, we need to look at what transpose does; for which we'll need to give meaning to transpose(f). As f is linear (V: |V) and V isn't given to be a space of functions – or may, indeed, be a space of functions such as V = {lists ({reals}: |n)}, in some manner not necessarily directly helpful to its study as a linear space – we have to consider the meaning of transpose(f) with some care. Looking at transpose(L&on;f), we see that (L&on;f)(u, v) = L(f(u), v) is meaningful for u, v in V, so hermite wants to use transpose here in the sense transpose(L&on;f, u) = ({scalars}: L(f(v), u) ←v |V) = transpose(L, u)&on;f. This is *&on;hermite(L&on;f, u) and we're given that L is symmetric, so hermite(L&on;f, u) = *&on;transpose(L, u)&on;f = hermite(L, u)&on;f = L(u)&on;f and, for symmetric L&on;f, we have L(f(u)) = L(u)&on;f for each u in V. In support of this, define:
in which adjoin(L, f) is known as the L-adjoint of f or, when L is taken for granted by context, simply as the adjoint of f. For L&on;f to be hermite-symmetric, f must be equal to its own L-adjoint; such a linear map is described as self-L-adjoint or, when L is taken for granted, simply self-adjoint. If we're given a self-L-adjoint linear (V: f |V), we can duly infer hermite(L&on;f) = (: hermite(L, u)&on;f = L(u)&on;f ←u |V) = L&on;f and thus is symmetric. Thus L&on;f is symmetric precisely if f = adjoin(L, f), i.e. L(f(u),v) = L(u, f(v)) for all u, v in V.
Given positive-definite symmetric conjugate-linear (dual(V): L |V) and self-L-adjoint linear (V: f |V), consider two non-zero eigenvectors u, v in V, with eigenvalues h, k respectively. We obtain:
whence (*h −k).L(u, v) = 0. In the case u = v, hence h = k, we
have L(v, v) non-zero as L is positive-definite and u = v is non-zero; thus *k =
k is self-conjugate, i.e. real. Thus every eigenvalue of linear (V: f |V) is
real (if there is any positive-definite symmetric conjugate-linear
(dual(V): L |V) for which f is self-L-adjoint). In the case where h and k are
distinct (hence, given that they're real, *h and k are distinct), we obtain L(u,
v) = 0, i.e. eigenvectors of f are orthogonal
with respect to L if their
eigenvalues are different. When the number of distinct roots of the
characteristic polynomial of f is equal to the dimension of
V, we get a basis of eigenvectors, each with
a distinct eigenvalue; their L-orthogonality ensures that, by suitably scaling
each, we get a basis which simultaneously diagonalises L&on;f and
unit-diagonalises L. It remains to consider the case where some roots
coincide.
The derivation above does exploit the fact that L was positive-definite, and one can obviously use a negative-definite form in its place, but one might wonder whether a similar approach might be applicable to a mixed-sign form, at least when it's non-singular. However, a simple example suffices to show that it's not possible: consider the forms L([X,x],[X,x]) = norm(X) −norm(x) and g([X,x],[X,x]) = 2.(x.*X +X.*x) = norm(X+x) −norm(X−x) = L([X+x,X−x],[X+x,X−x]), so L([X,x],[X,x]) = g([X+x,X−x]/2,[X+x,X−x]/2). Feel free to try to find combinations of x and X with respect to which both forms are diagonal, before you read on.
Consider [Y,y] = [C.X +s.x, c.x −S.X], for some constants C, S, c and s, for which norm(X) −norm(x) = norm(Y) −norm(y); this is an arbitrary alternative unit-diagonalisation of L. Expanding norm in each case, we obtain
and equating corresponding terms gives us C.*s = S.*c (from X.*x; and the same conjugated from x.*X) and norm(C) −norm(S) = 1 = norm(c) −norm(s). Since the hyperbolic sine-analogue sinh is monotonically increasing and one-to-one ({reals}| sinh |{reals}), there are some real a, A for which √norm(s) = sinh(a) and √norm(S) = sinh(A), hence norm(c) = 1 +norm(s) = 1 +sinh(a).sinh(a) = cosh(a).cosh(a) and, likewise, √norm(C) = cosh(A); consequently, s/sinh(a), c/cosh(a), S/sinh(A) and C/cosh(A) are all phases – complex numbers with norm 1, hence the conjugate of each is its inverse. Our remaining equation C.*s = S.*c can be re-written as S/C = *(s/c) whence tanh(A) = ±tanh(a); and tanh is an odd monotonic increasing function, so this implies A = ±a. If a = 0, we have C and c as phases (with no constraint on relative phase); otherwise, let e, f be phases for which s = sinh(a).e, c = cosh(a).e/f so s/c = tanh(a).f so S/C = tanh(a)/f; so, with E as the phase for which C = E.cosh(a), we get S = sinh(a).E/f. So our general alternative co-ordinates are [Y,y] = [cosh(a).E.X +sinh(a).e.x, (cosh(a).e.x −sinh(a).E.X)/f]. Since only norm(y) is used, y's factor of 1/f has no effect here, but might in g.
Next, we need to invert the transformation to get [X,x] as a functin of [Y,f.y] = [cosh(a).E.X +sinh(a).e.x, cosh(a).e.x −sinh(a).E.X]. We can eliminate x by combining Y.cosh(a) −f.y.sinh(a) = E.X.(cosh(a).cosh(a) +sinh(a).sinh(a)) = E.X.cosh(2.a) and eliminate X by combining Y.sinh(a) +f.y.cosh(a) = e.x.(sinh(a).sinh(a) +cosh(a).cosh(a)) = e.x.cosh(2.a), so that X = (Y.cosh(a) −f.y.sinh(a))/cosh(2.a)/E and x = (Y.sinh(a) +f.y.cosh(a))/cosh(2.a)/e. We then obtain:
For this to be diagonal, we would need cosh(a).cosh(a).e/E = sinh(a).sinh(a).E/e, but then sinh(a).sinh(a).E.E/e/e = cosh(a).cosh(a) = 1 +sinh(a).sinh(a) > sinh(a).sinh(a) is real and positive; but E.E/e/e is a phase – multiplying a positive real by it cannot increase it. So no unit-diagonalisation of L can make g diagonal.
Written by Eddy.