📖 Quadratic forms

⏱ | words

WARNING

This section of the lecture notes is still under construction. It will be ready before the lecture.

Conic sections

Conic sections are a collection of curves obtained by intersecting a cone with a plane.

An equation describing every conic section is a quadratic equation in two variables.

Fig. 49 Conic sections

Definition

A collection of points \((x,y)\in\mathbb{R}^2\), the sum of distances from which to two fixed points (termed foci) is constant, is an ellipse.

When the two foci coincide, the ellipse becomes a circle.

Canonical equation of an ellipse with parameters \(a\) and \(b\)

\[ \frac{x^2}{a^2}+\frac{y^2}{b^2} = 1 \]

When \(a=b\), the ellipse becomes a circle with radius \(a=b\).

Definition

Parabola is a collection of points \((x,y)\in\mathbb{R}^2\) laying at equal distances from a fixed point (focus) and a fixed line (directrix).

Parabola is a section of a cone by a plane parallel to another plane tangential to the conical surface.

Canonical equation of an ellipse with parameters \(a\) and \(b\)

\[ x^2 = 2py \]

Definition

Hyperbola is a collection of points \((x,y)\in\mathbb{R}^2\), the difference of distances from which to two fixed points (termed foci) is constant.

Canonical equation of an ellipse with parameters \(a\) and \(b\)

\[ \frac{x^2}{a^2}-\frac{y^2}{b^2} = 1 \]

We typically encounter a hyperbola with the equation \(y=1/x\) or \(yx=1\), but it is easy to show that this is a special case with \(a=b\) after a change of basis with transformation matrix given by \(P=\tfrac{1}{\sqrt{2}}\begin{pmatrix}1&-1\\1&1\end{pmatrix}\)

Note

The highest power of \(x\) and \(y\) in the equation of a conic section is 2, hence the name quadratic curves.

Quadratic forms

Definition

Quadratic form in a function \(Q \colon \mathbb{R}^N \to \mathbb{R}\)

\[ Q(x) = \sum_{i=1}^N \sum_{j=1}^N a_{ij} x_i x_j \]

Note that we can assume that \(a_{ij} = a_{ji}\): indeed, if for some quadratic form \(\sum_{i=1}^N \sum_{j=1}^N c_{ij} x_i x_j\) symmetry does not hold, redefine

\[ a_{ij} = a_{ji} = \frac{c_{ij}+c_{ji}}{2} \]

then

\[\begin{split} \begin{array}{c} Q(x) = \sum_{i=1}^N \sum_{j=1}^N a_{ij} x_i x_j = \\ \begin{array}{cccccccc} a_{11} x_1 x_1 &+& a_{12} x_1 x_2 &+& \ldots &+& a_{1N} x_1 x_N & + \\ a_{21} x_2 x_1 &+& a_{22} x_2 x_2 &+& \ldots &+& a_{2N} x_2 x_N & + \\ \vdots & & \vdots & & \ddots & & \vdots & \\ a_{N1} x_N x_1 &+& a_{N2} x_N x_2 &+& \ldots &+& a_{NN} x_N x_N \end{array} = \\ \sum_{i=1}^N a_{ii} x_i^2 + 2 \sum_{i<j} a_{ij} x_i x_j = \\ = \sum_{i=1}^N c_{ii} x_i x_i + \sum_{i<j} (c_{ij}+c_{ji}) x_i x_j = \sum_{i=1}^N \sum_{j=1}^N c_{ij} x_i x_j \end{array} \end{split}\]

Definition

Quadratic form \(Q \colon \mathbb{R}^N \to \mathbb{R}\) can be equivalently represented as a matrix product

\[ Q(x) = x^T A x \]

where \(x \in \mathbb{R}^N\) is a column vector, and \((N \times N)\) symmetric matrix \(A\) consists of elements \(\{a_{ij}\}\), \(i,j=1,\ldots,N\)

Example

\[ f: \mathbb{R}^3 \ni (x,y,z) \to x^2+3y^2-z^2-4xy+2yz \in \mathbb{R} \]

has a matrix representation with

\[\begin{split} A = \begin{pmatrix} 1 & -2 & 0 \\ -2 & 3 & 1 \\ 0 & 1 & -1 \end{pmatrix} \end{split}\]

Exercise: verify

Note

The degree of a quadratic form \(Q(x)\) which is a multivariate polynomial function is given by the sum of the powers of the variables, and for quadratic forms is not higher than 2, hence the name quadratic form. This implies that no term of the quadratic form may have a product of more than two variables!

Why are quadratic forms useful in the optimization course?

Look at the third term in the multivariate Taylor expansion of a function \(f(x) \colon \mathbb{R}^N \to \mathbb{R}\). It is a quadratic form!

We use quadratic forms for a local approximation of any function, in particular the functions we will want to optimize — later in the course.

Canonical form of quadratic forms

Definition

A canonical form of a quadratic form \(Q(x)\) is given by a sum of squares of the variables

\[ Q(x) = \sum_{i=1}^N a_i x_i^2 \]

Fact

By change of bases any quadratic form \(Q(x)\) with a symmetric real matrix \(A\) can be transformed to a sum of squares with positive or negative coefficients

\[ Q(x) = x^T A x = x^T P^T D P x = (Px)^T D (Px) = \sum_{i=1}^N \lambda_i (Px)_i^2 \]

where \(\lambda_i\) are the eigenvalues and \(P\) is the matrix of eigenvectors of \(A\).

Proof

It follows from the symmetry of \(A\) that it has \(N\) real eigenvalues and can be diagonalized with the transformation matrix \(P\) composed of eigenvectors.

The change of variable \(y = Px\) leads to a transformed quadratic form \(Q(y) = y^T D y = \sum_{i=1}^N \lambda_i y_i^2\) which contains only squares of the variables.

Fig. 50 Change of bases to convert the quadratic form to a canonical form

Definiteness of quadratic forms

The properties and shape of \(Q(x)\) depend on the configuration of matrix \(A\)

Fig. 51 A convex \(Q(x) = x' I x\)

Fig. 52 A concave \(Q(x) = x'(-I)x\)

Definition

Quadratic form \(Q(x)\) is called positive definite if

\[ Q(x) = x^T A x >0 \text{ for all } x\ne 0 \]

Quadratic form \(Q(x)\) is called negative definite if

\[ Q(x) = x^T A x <0 \text{ for all } x\ne 0 \]

• the examples above show these cases

• note that because every quadratic form can be represented by a linear combination of squares, the characteristic properties are the signs of the coefficients in the canonical form!

Fact (Law of inertia)

The number of coefficients of a given sign in the canonical form of a quadratic form does not depend on the choice of the basis

• such robust characteristics are called invariants

• number of coefficients of a given sign is an invariant of the quadratic form called the index of the quadratic form

Definition

Positive and negative definite quadratic forms are called definite

Note that for some matrices it may be that

• for some \(x\): \(x^T A x < 0\)

• for some \(x\): \(x^T A x > 0\)

In this case \(A\) is called indefinite

Fig. 53 Indefinite quadratic function \(Q(z) = x_1^2/2 + 8 x_1 x_2 + x_2^2/2\)

Example

\[\begin{split} \begin{array}{ll} Q(x) = x_1^2 + 2 x_2^2 + 1/2 x_3^2 & \text{positive definite} \\ Q(x) = x_1^2 - 2 x_2^2 & \text{indefinite} \\ Q(x) = x_1 x_2 & \text{indefinite} \\ Q(x) = 2 x_1 x_2 - x_1^2 - 4 x_2^2 = -(x_1-x_2)^2 - 3x_2^2 & \text{negative definite} \\ \end{array} \end{split}\]

Definition

Quadratic form \(Q(x)\) is called non-negative definite (positive semi-definite) if

\[ Q(x) = x^T A x \geqslant 0 \text{ for all } x\ne 0 \]

Quadratic form \(Q(x)\) is called non-positive definite (negative semi-definite) if

\[ Q(x) = x^T A x \leqslant 0 \text{ for all } x\ne 0 \]

Example

\[\begin{split} \begin{array}{ll} Q(x) = x_1^2 + 2 x_2^2 & \text{positive semi-definite if } x \in \mathbb{R}3\\ Q(x) = x_1^2 + 2x_1 x_2 + x_2^2 & \text{positive semi-definite} \\ \end{array} \end{split}\]

In the last example, the points \(t(1,-1)\) for any \(t \in \mathbb{R}\) yield \(Q(x) = 0\)

Fact (eigenvalues criterion)

A quadratic form \(Q(x)\) with a symmetric real matrix \(A\) is

• positive definite \(\iff\) all eigenvalues are strictly positive

• negative definite \(\iff\) all eigenvalues are strictly negative

• nonpositive definite \(\iff\) all eigenvalues are nonpositive

• nonnegative definite \(\iff\) all eigenvalues are nonnegative

Proof

Follows immediately from the diagonalization of \(A\) \(\blacksquare\)

Example

\[ Q(x,y) = 8x^2 - 28xy + 29y^2 \]

\[\begin{split} A = \begin{pmatrix} 8 & -14 \\ -14 & 29 \end{pmatrix} \end{split}\]

Let’s diagonalize \(A\) by finding eigenvalues and eigenvectors

\[\begin{split} \left| \begin{array}{cc} 8-\lambda & -14 \\ -14 & -29-\lambda \end{array} \right| = (8-\lambda)(29-\lambda) - 14^2 = \lambda^2 - 37\lambda + 36 =0 \end{split}\]

Eigenvalues are \(\lambda_1 = 1\) and \(\lambda_2 = 36\)

Eigenvectors are \(v_1 = (2,1)\) and \(v_2 = (-1,2)\)

Transformation matrix is \(P = \begin{pmatrix} 2 & -1 \\ 1 & 2 \end{pmatrix}\)

Let \((u,v) = (2x-y,x+2y)\), then the quadratic form can be written as \(Q(u,v) = u^2 + 36v^2 >0\) for any \(u,v\)

Hense, \(Q(x)\) is a positive definite

Fact

If quadratic form \(x^TAx\) is positive definite, then \(\det(A) > 0\)

Proof

Positive definite \(\iff\) all eigenvalues are strictly positive \(\implies\) \(det(A)>0\) as the product of eigenvalues. \(\blacksquare\)

• in particular, \(A\) is nonsingular

Silvester’s criterion

Diagonalization of the higher order matrices may be hard. We have an alternative for determining the definiteness of a quadratic form

Definition

Consider a \(N \times N\) matrix \(A\) and let \(0 < k \le N\).

The leading principal minor \(M_k\) of order \(k\) of \(A\) is the determinant of a matrix obtained from \(A\) by deleting its last \(N-k\) rows and columns.

Example

\[\begin{split} A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \end{split}\]

The leading principal minors of oder \(k = 1,\dots,n\) of \(A\) are

\[\begin{split} \begin{array}{l} M_1 = \mathrm{det}(a_{11}) = a_{11} \\ M_2 = \mathrm{det}\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) = a_{11}a_{22} - a_{12}a_{21} \\ M_3 = \mathrm{det}\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right)\\ \vdots \\ M_n = \mathrm{det}(A) \end{array} \end{split}\]

Fact (definiteness)

Let \(A\) be an \((N \times N)\) symmetric square matrix. The corresponding quadratic form \(Q(x) = x^T A x\) is positive definite if and only if all leading principal minors of \(A\) are positive

\[ x^T A x > 0 \text{ for all } x \ne 0 \quad \iff \quad M_k > 0 \text{ for all } k=1,\ldots,N \]

Quadratic form \(Q(x) = x^T A x\) is negative definite if and only if the leading principal minors of \(A\) alternate in sign according to the following rule

\[ x^T A x < 0 \text{ for all } x \ne 0 \quad \iff \quad (-1)^k M_k >0 \text{ for all } k=1,\ldots,N \]

• the last condition can be restated as the leading principle minor \(M_k\) to have the same sign as \((-1)^k\)

• if \(A\) does not satisfy either of the conditions, it is indefinite or semi-definite

Silvester’s criterion for semi-definiteness is more involved

Definition

Consider a \(N \times N\) matrix \(A\) and let \(0 < k \le N\).

The principal minor \(P_k\) of order \(k\) of \(A\) is the determinant of a matrix obtained from \(A\) by deleting any of its \(N-k\) rows and columns with the same indexes.

• observe the difference from the leading principal minor

Example

\[\begin{split} A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \end{split}\]

All the principal minors of oder \(k = 1,2,3\) of \(A\) are

\[\begin{split} \begin{array}{l} P^{a}_1 = \mathrm{det}(a_{11}) = a_{11} \\ P^{b}_2 = \mathrm{det}(a_{22}) = a_{22} \\ P^{c}_3 = \mathrm{det}(a_{33}) = a_{33} \\ P^{a}_2 = \mathrm{det}\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right) = a_{11}a_{22} - a_{12}a_{21} \\ P^{b}_2 = \mathrm{det}\left( \begin{array}{cc} a_{11} & a_{13} \\ a_{31} & a_{33} \end{array} \right) = a_{11}a_{33} - a_{13}a_{31} \\ P^{c}_2 = \mathrm{det}\left( \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right) = a_{22}a_{33} - a_{23}a_{32} \\ P_3 = \mathrm{det}\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \end{array} \end{split}\]

Fact (semi-definiteness)

Let \(A\) be an \((N \times N)\) symmetric square matrix. The corresponding quadratic form \(Q(x) = x^T A x\) is positive semi-definite if and only if all principal minors of \(A\) are non-negative.

\[ x^T A x \geqslant 0 \text{ for all } x \ne 0 \quad \iff \quad \forall P_k: P_k \geqslant 0 \text{ for all } k=1,\ldots,N \]

Quadratic form \(Q(x) = x^T A x\) is negative semi-definite if and only if all principal minors of oder \(k\) of \(A\) are zero or have the same sign as \((-1)^k\)

\[ x^T A x \leqslant 0 \text{ for all } x \ne 0 \quad \iff \quad \forall P_k : (-1)^k P_k \geqslant 0 \text{ for all } k=1,\ldots,N \]

Example

\[\begin{split} A = \left( \begin{array}{ccc} 4 & 0 & 1 \\ -2 & 1 & 0 \\ -2 & 0 & 1 \end{array} \right) \end{split}\]

The leading principal minors of \(A\) are

\[\begin{split} \begin{array}{l} M_1 = \mathrm{det}(4) = 4 \\ M_2 = \mathrm{det}\left( \begin{array}{cc} 4 & 0 \\ -2 & 1 \end{array} \right) = 4 \cdot 0 - 1(-2) = 2 \\ M_3 = \mathrm{det}\left( \begin{array}{ccc} 4 & 0 & 1 \\ -2 & 1 & 0 \\ -2 & 0 & 1 \end{array} \right) = 4 - (-2) = 6 \end{array} \end{split}\]

All leading principal minors are positive, hence \(x^TAx\) is positive definite.

It can also be shown that the eigenvalues of \(A\) are \(\{1,2,3\}\), that is all positive, and therefore the same conclusion is reached by the eigenvalues criterion.

Example

\[\begin{split} B = \left( \begin{array}{ccc} 3 & 0 & -5 \\ \frac{1}{5} & -1 & 0 \\ 1 & 1 & -2 \end{array} \right) \end{split}\]

The leading principal minors of \(B\) are

\[\begin{split} \begin{array}{l} M_1 = \mathrm{det}(3) = 3 \\ M_2 = \mathrm{det}\left( \begin{array}{cc} 3 & 0 \\ \frac{1}{5} & -1 \end{array} \right) = 3 (-1) - 0(\frac{1}{5}) = -3 \\ M_3 = \mathrm{det}\left( \begin{array}{ccc} 3 & 0 & -5 \\ \frac{1}{5} & 1 & 0 \\ 1 & 1 & -2 \end{array} \right) = 6 -1 - 5 = 0 \end{array} \end{split}\]

The leading principal minors do not match neither the rule for positive definiteness (all positive) nor the rule for negative definiteness (alternating signs). But the rule for the negative semi-definiteness may still be satisfied, hence let’s examine the rest of principal minors.

The other (non-leading) principal minors of order \(k=1\) of \(B\) are

\[\begin{split} \begin{array}{l} M^2_1 = \mathrm{det}(-1) = -1 \\ M^3_1 = \mathrm{det}(-2) = -2 \\ \end{array} \end{split}\]

and it is clear that the rule for negative semi-definiteness is not satisfied: principle minors of oder 1 differ in signs.

Thus, \(x^TBx\) is indefinite.

It can also be shown that the eigenvalues of \(A\) are \(\{-\sqrt{2},0,\sqrt{2}\}\), that is they differ is sing, and therefore \(B\) is indefinite also by the eigenvalues criterion.

Example

\[\begin{split} C = \left( \begin{array}{cc} -1 & -\sqrt{2} \\ -\sqrt{2} & -2 \end{array} \right) \end{split}\]

The leading principal minors of \(C\) are

\[\begin{split} \begin{array}{l} M_1 = \mathrm{det}(-1) = -1 \\ M_2 = \mathrm{det}\left( \begin{array}{cc} -1 & -\sqrt{2} \\ -\sqrt{2} & -2 \end{array} \right) = 2 - 2 = 0 \end{array} \end{split}\]

The leading principal minors do not match neither the rule for positive definiteness (all positive) nor the rule for negative definiteness (alternating signs). But the rule for the negative semi-definiteness may still be satisfied, hence let’s examine the rest of principal minors, namely one more principle minor of order 1:

\[ M^2_1 = \mathrm{det}(-2) = -2 \]

Ok, the pattern for negative semi-definiteness is satisfied!

Thus, \(x^TCx\) is negative semi-definite.

The plot of the quadratic form \(x^TCx\) is below. Note the line of zero values of the quadratic form attained at many different non-zero points \((-p,p/\sqrt{2})\), where \(p \in \mathbb{R}\).

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib import cm

A = np.array([[-1,-np.sqrt(2)],[-np.sqrt(2),-2]])
f = lambda x: x@A@x
x = y = np.linspace(-5.0, 5.0, 100)
X, Y = np.meshgrid(x, y)
zs = np.array([f((x,y)) for x,y in zip(np.ravel(X), np.ravel(Y))])
Z = zs.reshape(X.shape)

fig = plt.figure(dpi=160)
ax3 = fig.add_subplot(111, projection='3d')
ax3.plot_wireframe(X, Y, Z, 
            rstride=2, 
            cstride=2,
            alpha=0.7,
            linewidth=0.25)
f0 = f(np.zeros((2)))+0.1
ax3.plot([-5,5],[5/np.sqrt(2),-5/np.sqrt(2)],[f0,f0],color='black',linewidth=0.5)
plt.setp(ax3,xticks=[],yticks=[],zticks=[])
plt.show()

References and reading

References

• [Simon and Blume, 1994]: 13.3, 16.1, 16.2

• [Sundaram, 1996]: 1.5

Further reading and self-learning

• Excellent visualizations of concepts covered in this lecture, strongly recommended for further study 3Blue1Brown: Essence of linear algebra