# Ask Uncle Colin: A restricted determinant

Dear Uncle Colin,

Can you show that 4 is the largest determinant of a 3 by 3 matrix made of 1s and -1s?

- Just A Crisis Of Brainy Ideas

Hi, JACOBI, and thanks for your message!

### Pluggety and chuggety

Let’s let the matrix be $\matthreethree{a}{&b}{&c}{d}{&e}{&f}{g}{&h}{&i}$.

Its determinant is $a\left| \mattwotwo{e}{f}{h}{i} \right| + b \left| \mattwotwo{f}{d}{i}{g} \right| + c \left|\mattwotwo{d}{e}{g}{h}\right|$, and the largest each of those two-by-two determinants could possibly be is 2 - which gives us an immediate upper bound of 6 for the full determinant.

How would we end up with one of the submatrices having a determinant of 2? We’d need a two-by-two matrix to be something like $\mattwotwo{1}{1}{-1}{1}$ - i.e., any three elements matching in sign and the other one opposite.

Suppose (without loss of generality), $\mattwotwo{e}{f}{h}{i} = \mattwotwo{1}{1}{-1}{1}$, leaving $d$ and $g$ as variables for now. What happens to the other two matrices? Those are now $\mattwotwo{f}{d}{i}{g} = \mattwotwo{1}{d}{1}{g}$ and $\mattwotwo{d}{e}{g}{h} = \mattwotwo{d}{1}{g}{-1}$.

The first of those has a determinant of $\pm 2$ if $d \ne g$ and 0 if they’re equal; with the second, it’s the other way around - if they’re equal, the determinant is $\pm 2$ and it’s zero if they’re different. In either case, the determinant of one of the matrices is $\pm 2$ and the other is 0, so the largest determinant for the 3 by 3 matrix is 4.

But that feels a bit unsatisfactory.

### Geometry and symmetry

What does a 3-by-3 matrix do? It maps three vertices of the unit cube ( $\mathbf i = (1,0,0)$, $\mathbf j = (0,1,0)$ and $\mathbf k = (0,0,1)$ ) to three new vertices, and drags the rest of cube into a parallelepiped. The volume of the parallelepiped is the determinant of the matrix.

An arbitrary 3-by-3 matrix can send the vertices anywhere in 3D space, but we’re restricted to sending them to the eight vertices of a cube, which are $(\pm_1 1, \pm_2 1, \pm_3 1)$. However, we’re stuck with keeping one of the vertices at the origin, the centre of the cube.

So what’s the biggest we can make our parallelepiped under this restriction?

Suppose (again, wlog) I send $(1,0,0)$ to $(1,1,1)$. A healthy start, with an edge of length $\sqrt{3}$. Where can I send the other vertices to maximise the parallelepiped’s volume?

There’s no point in sending a vertex to $(-1,-1,-1)$ because the resulting parallelepiped would have zero volume, so we have six vertices available to us. Three are ‘neighbours’ to $(1,1,1)$ (i.e., you can reach them by flipping only one sign), and three require two flips.

If we pick two neighbouring vertices (and exclude their opposites), the third vertex must lie on a face of the big cube. If we pick two non-neighbouring vertices (and exclude their opposites), the third vertex is either a neighbour of both (and we’ve covered that case), or a neighbour of neither (and forms an equilateral triangle).

So we only have two possible shapes!

Rather than the parallelepiped ((I’ve asked @alisonkiddle to reset the counter, don’t worry)), let’s think about the tetrahedron formed by $\mathbf 0, \mathbf i, \mathbf j$ and $\mathbf k$. The scale factor of the transformation that takes it to a new tetrahedron will be the same as that of the cube, because linear magic. (The original tetrahedron has a volume of $\frac{1}{6}$, which you might like to verify.)

The first shape has the three free vertices going to three points on the same face, which I’ll think of as the base. The base has an area of 2 units, and is one unit from the origin, so the new tetrahedron has an volume of $\frac{2}{3}$ units, four times that of the original tetrahedron.

The second shape is (for me at least) a bit harder to reason about. In fact, I’m going to map $\mathbf i, \mathbf j$ and $\mathbf k$ to $(-1,1,1)$, $(1,-1,1)$ and $(1,1,-1)$, respectively, because it’s neater in my head.

The edges of the equilateral triangle they form have length of $2\sqrt{2}$. That means the area of the base can be worked out using $\frac{1}{2}ab \sin(C)$ to be $2{\sqrt{3}}$. But what about the height?

The centroid of the base lies at $\left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right)$, and by symmetry has to be the foot of the perpendicular from the origin. That distance is $\frac{1}{\sqrt{3}}$.

The volume of this tetrahedron is then $\frac{1}{3}(2\sqrt{3})\left(\frac{1}{\sqrt{3}}\right) = \frac{2}{3}$ as well! The scale factor is again 4.

### Jiggery and pokery

I think this shows that the determinant of a matrix made of 1s and -1s is either 4, 0 or -4. There are $2^9=512$ possible such matrices, although if you restrict the first column to be all 1s (wlog), there are only 64. Looking at the next column, two of the eight possibilities give a determinant of zero (they’re multiples of ‘all 1s’); given we’re not among those two, a random final column has a 50-50 chance of being a multiple of one of the first two. So, of the original 64, 24 have determinant of $\pm 4$ (12 of each), and the remaining 40 have determinant zero.

That’s probably more than you wanted to know, isn’t it? Never mind; I still hope it helps.

- Uncle Colin