Back to Hans Lundmark's main page

The Canada Day Theorem is a curious combinatorial identity that unexpectedly cropped up when Andy Hone, Jacek Szmigielski and I were studying so-called peakon solutions to a nonlinear integrable PDE found by Vladimir Novikov in 2008.

For the story of how the theorem got its name, and also a description of our proof, see the slides from one of my talks. The result was first published in the appendix of our paper about Novikov peakons, and later with an improved proof in a separate paper.

The theorem deals with *n*×*n* matrices,
where *n* is a fixed number.
For the illustrations, I'll take *n* = 4.

Let *X* denote an arbitrary **symmetric** *n*×*n* matrix:

Let *T* be the *n*×*n* matrix with
*T*_{ij} equal to 0, 1, or 2, depending on whether *i*
is less than, equal to, or greater than *j*:

If *I* and *J* are two index sets, each containing *k*
of the numbers from 1 to *n*,
then for any matrix *A* we let *A*_{I,J}
denote the *k*×*k*
submatrix of *A* formed by the entries lying in the rows indexed by *I*
and the columns indexed by *J*. For example,

The determinant det(*A*_{I,J}) of such a submatrix,
is called a *k*×*k* **minor** of *A*.
Those minors for which *I* = *J*
are called the **principal minors** of *A*.

(As you may know, the coefficient of λ^{n−k}
in the characteristic polynomial det(*A* − λ*I* )
equals (up to sign) the sum of the
*k*×*k* principal minors of *A*.)

For any *k* = 1, …, *n*,
the sum of the **principal** *k*×*k* minors of the matrix *TX*
equals the sum of **all** *k*×*k* minors of *X*.

Note that it's essential that *X* is symmetric, otherwise the theorem
would not be true.

Let's look at the case *n* = 3, where the following 3×3 matrices
are involved:

There are three possible values of *k*:

** k = 1.**
The 1×1 minors of

** k = 3.**
There is only one 3×3 minor in a 3×3 matrix, namely the determinant
of the whole matrix (and this is a principal minor).
Thus, what the Canada Day Theorem states in this case is that the equality
det

** k = 2.**
This is more interesting. Now we are comparing two sums of 2×2 minors,
as shown below. (The formulas are meant to indicate the 2×2 determinants
formed by the red entries only;
the grey entries are merely shown to make it easier to see where each minor sits inside the original
matrix.)

It's straightforward to verify that this is true as well.

You may have noticed in the big equation above (*n* = 3, *k* = 2)
that it's possible to group the terms on the left-hand side so
that each group of terms equals a corresponding determinant on the
right-hand side.
**It's not that simple for n ≥ 4**, as you may convince yourself
by looking at some larger examples.

If (like me) you can't resist a little combinatorial challenge, then you might find it an interesting exercise to try to prove the theorem yourself. Please let me know if you find a really simple solution (or if you've seen this result somewhere else in the literature)!

Last modified 2015-01-21. Hans Lundmark (hans.lundmark@liu.se)