Prove an upper bound for the determinant of a matrix A

Question

1. Let $A$ be a $3 \times 3$ real matrix with all $0\le a_{ij} \le 1$.

   Show that $\det(A) \leq 2$ and find such matrices with $\det(A) = 2$.

2. Let $A$ be a $n \times n$ matrix with all $0\le a_{ij} \le 1$.

   Estimate precisely a maximum possible value of $\det(A)$.

I would like to try and solve this problem without the usage of the permutation formula for the determinant.

Answer 1

Edit 3: This hint might not be the best way to approach the problem.

Hint: Start with $2\times 2$ matrices and work by induction.

Edit 2:

Show that for a $2\times 2$ matrix with those properties, $|\det A| \leq 1$. Evaluate different cases and convince yourself these are in fact the extrema ($-1$ and $1$). The matrices that achieve these values are: $$ \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},\quad \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix},\quad\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix}, $$ and $$ \begin{pmatrix} 0 & 1 \\ 1 &0\end{pmatrix},\quad \begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix},\quad\begin{pmatrix} 0 & 1 \\ 1 & 1\end{pmatrix}. $$

Now, if $A$ is your $3\times 3$ we have $\det A = a_{11}\det A_{11} - a_{22}\det A_{22} + a_{33}\det A_{33}$. Can you find the matrices such that $|\det A| = 2$ ? ATM I don't know how to prove this is in fact the maximum.

Answer 2

@hjhjhj57, not sure if you've found the matrices yet - the ones where detA = 2. But here is my work. If you just play around with the 3 cases, and see which entries must be zero and which entries must be equal to one, you should get the below 3 matrices - and also using your hint for induction on the 1x1 and 2x2 cases.

Look at:

$$A= \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{bmatrix} $$

$\implies$ detA = a(ei-fh) - b(di - fg) + c(dh-eg).

Call the first term I, the second term II, and the third term III.

Case 1: Now if we want to maximize detA, by maximizing I and II (so, making b(di-fg) = -1), then from how the variables are related and already chosen, you'll see that III will be negative if c were not equal to zero. So we set c equal to zero to maximize detA.

Case 2: If we want to maximize detA, by maximizing II and III - so making II and III each equal to 1 - then we'll see that I is a negative number. So we must set a = 0 to maximize detA.

Case 3:
Similar argument for maximizing I and III.

In all 3 cases, the maximum determinant was equal to 2, so we see that there are exactly 3 matrices with max det(A) = 2, which are:

$$ \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{bmatrix} $$

$$ \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix} $$

$$ \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} $$