1
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ Please take a look at Hadamard Max Determinant Problem :) $\endgroup$ – r9m Dec 22 '14 at 6:45
  • 1
    $\begingroup$ @r9m, I was able to derive the upper bound for the nxn case by interpreting the determinant as the volume of a parallelepiped, whose sides are given by the columns of A. Then I take the norm of each column vector, which gives the obvious bound sqrt(n), since each entry is at most equal to 1. The, just as we would multiply the length of adjacent sides of an object to compute its volume, I multiply the norm of each column vector in my nxn matrix, getting the volume (determinant), (sqrt(n)^n = n^(n/2). This matches Hadamard's bound, but I think it's a much easier way to remember the bound.. :) $\endgroup$ – User001 Dec 24 '14 at 1:00
  • $\begingroup$ @hjhjhj57 here's what I did for the nxn case. I couldn't see how to use induction to conclude the general case. I think the volume interpretation of the determinant to derive the bound for the nxn case is easy to remember. Let me know if you have additional material you'd like to share. Thanks again for the induction hint for the 3x3 case :) $\endgroup$ – User001 Dec 24 '14 at 1:04
  • $\begingroup$ Yes ! That upper bound is the Hadamard's Inequality ! :) But your problem asks entries in $[0,1]$ interval. The max-det for $\{0,1\}$-matrices is $\frac{(n+1)^{(n+1)/2}}{2^n}$ (which are matrices taking the extreme entries $0$ and $1$ of the interval $[0,1]$). So far I don't have much idea how to formally tackle this problem. $\endgroup$ – r9m Dec 24 '14 at 1:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you indicate how to proceed with the induction steps please :) $\endgroup$ – r9m Dec 22 '14 at 6:49
  • $\begingroup$ Interesting hint, @hjhjhj57. Starting with 2x2, I see detA is just the usual ad-bc formula, so I'll maximize a and d, setting both equal to 1. the off-diagonal entries, I just need one of them to be 0. so max(detA) = 1, for the 2x2 case, I think.. $\endgroup$ – User001 Dec 22 '14 at 6:52
  • $\begingroup$ I got the upper bound, 2, for the 3x3 case. (just expanded the determinant formula along row 1, then use the bound from the 2x2 case.) I'm working on the case where detA = 2. Very nice hint :) $\endgroup$ – User001 Dec 22 '14 at 6:59
  • $\begingroup$ I'm glad it helped you. $\endgroup$ – hjhjhj57 Dec 22 '14 at 7:00
  • $\begingroup$ You show that in the $3 \times 3$ case that $\det A \le 3$. Shouldn't you show that it is $\le 2$? $\endgroup$ – copper.hat Dec 22 '14 at 7:10
0
$\begingroup$

@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} $$

$\endgroup$
  • 1
    $\begingroup$ Completely agree. I believe that in order to completely solve this problem you would need some group theory to handle the permutations, but your reasoning is correct. $\endgroup$ – hjhjhj57 Dec 23 '14 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.