9
$\begingroup$

Given a multiset $S\subset [-1,1]^{n^2}$, we set $$m(S)=\min\vert \det(M)\vert$$ where the minimum is over all matrices with entries forming the multiset $S$ and $$a(n)=\max m(S)$$ where the maximum is over all multisets with $n^2$ elements in $[-1,1]$.

Obviously $a(2)=2$ by considering $S=\lbrace 1,1,1,-1\rbrace$.

I know nothing else (except for the trivial bounds $0 < a(n)\leq n^{n/2}$).

Even the computation of $a(3)$ (or of a good lower bound on $a(3)$) seems quite a feat to me.

$\endgroup$
13
  • 1
    $\begingroup$ The math just rendered, and I see I have misread the question. I retract the above two comments, although you may find them useful. I conjecture a(n) near 0 for n larger than 2. Gerhard "These Are Not Binary Matrices" Paseman, 2011.12.05 $\endgroup$ Dec 5, 2011 at 22:15
  • 1
    $\begingroup$ Further, there was a sci.math post a few years back by Hugo Pfoertner on looking at matrices with entries in 1,2,...,n^2, and looking at variations of the determinant function when n=3. I think his intuition on this problem is worth something. Gerhard "Ask Me About System Design" Paseman, 2011.12.05 $\endgroup$ Dec 5, 2011 at 22:23
  • 2
    $\begingroup$ I tried doing a computer search, and there seems to be a local maximum for the $n=3$ case near $\{1,1,1,1,1,1/4, -1/4, -16/25, -1\}$, where the minimum determinant has value $9/50$. I don't really see any compelling explanation for those values though. $\endgroup$ Dec 6, 2011 at 7:17
  • 1
    $\begingroup$ @Kevin P. Costello: Are you sure that you get a local maximum for your multiset? It is obvious that local maxima consist of algebraic numbers but it would be somwhat surprising that there are rational solutions. $\endgroup$ Dec 7, 2011 at 15:52
  • 2
    $\begingroup$ Roland: Sorry for being misleading by giving rationals...the maximum is only near that multiset, not exactly there (I had initially only searched in a mesh around that point, and didn't find any larger values). If you assume that (1) The maximum really occurs where there's five $1$s and a $−1$ and (2) that at the maximum the same two permutations have minimum determinant as in the $(0.25,−0.25,−0.64)$ case, you can solve explicitly for the maximum minimum determinant, getting that it occurs at $(2−\sqrt(5),\sqrt(5)−2,\frac{1−\sqrt{5}}{2})$ and has value $5 \sqrt{5} -11 \approx 0.1803$. $\endgroup$ Dec 7, 2011 at 21:09

2 Answers 2

2
$\begingroup$

I don't know the answer to your question, but the following is a bit long for a comment.

We can always assume one of the matrix elements is 1 since rescaling all elements so that the largest element equals 1 increases the minimal determinant by the scaling factor raised to the power $n$. It seems likely that any solution will have many 1s—of course less than $2n$, but possibly order $n$ of them—although I can't see how to prove this. For $n=3$ the matrix with elements in $[-1,1]$ of largest determinant is $$ \begin{bmatrix} -1 & 1 & 1\\ 1 & -1 & 1\\ 1 & 1 & -1 \end{bmatrix}. $$ This provides an upper bound of 4, which is slightly better than Hadamard's bound of about 5.2, but still apparently far too high.

It's possible to get a very slight improvement on Kevin Costello's lower bound for $n=3$. Consider the multiset $\{1,1,1,1,1,a,b,c,d\}$ with $$ a=0.19552006830186067389, $$ $$ b=-0.47998412524185001, $$ $$ c=-0.898326460649234689, $$ $$ d=-0.248885944004550461. $$ It has minimal determinant 0.185913849057346968. A hill-climbing procedure repeatedly arrives at solutions with five 1s. If the procedure is modified to assume five 1s, it readily finds solutions very close to the one above. The hill-climbing solutions (approximately) satisfy the property that the four matrices $$ \begin{bmatrix}1 & 1 & a\\ 1 & d & 1\\b & 1 & c\end{bmatrix},\quad \begin{bmatrix}1 & 1 & 1\\ 1 & 1 & a\\d & b & c\end{bmatrix},\quad \begin{bmatrix}1 & 1 & a\\ 1 & c & 1\\d & 1 & b\end{bmatrix},\quad \begin{bmatrix}1 & 1 & a\\ 1 & 1 & d\\b & c & 1\end{bmatrix}, $$ all have (minus the) minimal determinant. Imposing equality of these determinants, and maximizing their magnitude, yields the precise values above. (They are some messy algebraic numbers.)

$\endgroup$
0
$\begingroup$

This is meant to encourage Kevin Costello and Roland Bacher to do more numerical simulations to bound a(3).

I was impressed that Kevin found a maximum as large as 9/50, and that with 5 ones. I then computed the four essentially different forms that the determinant (or its negative) could take coming from a 3x3 matrix with 5 ones. Except for one of them, I found I could simplify the expressions by using the substitutions z_i = a_i - 1. I think when these forms are investigated, an explanation for the non-1 entries will be forthcoming. I also wonder if perhaps the non-one entries can be replaced with 4/9, -1/9, -5/9, and -1, which if it works would be explained by the heuristic of spacing out the non-1 values. A similar analysis might be done using 4 ones instead of 5.

ADDED 2011.12.23 Thanks to Will Orrick for catching the erroneous "four" above and reminding me of a fifth form. While the substitutions might help in analyzing the now 120 possible expressions for a determinant containing 5 ones, I now have a couple of nice observations that might help estimate a(3) and possibly a(n). I have convinced myself that a(n) is decreasing as n > 1 increases, but only have a suggestion as to how to show it.

For a(3), one of the configurations involving 4 ones has them arranged in a 2x2 square, leading to a determinant of (a-b)(c-d) and a tentative upper bound for this case of 1/4. While it is possible that 1/4 could be beaten by multisets which have only 3 or 2 ones in them, I am confident that the other posters are close to determining a(3) and that it will be less than 1/4.

For general $n$, one can assume (as Will Orrick noted) 1 is in the multiset of $n^2$ values and sort them and then place the sorted set in the array in various ways while preserving relations like $a_{i,j} > a_{i,j+1}$. Now one can subtract multiples of one row from another to get rows of small norm (when consider as vectors in $R^n$). It may then be feasible to show that the given matrix is equivalent via such row operations to one in which the product of the norms of the rows is at most 1, and possibly smaller. An alternative picture is to say that the rows belong to the region of the positive unit orthant which satisfies $ x_1 \leq x_2 \leq \ldots \leq x_n$, and that the angle between a group of, oh, say, $n/2$ of them is less than $\epsilon(n)$ which would give a similar bound on the determinant. END ADDED 2011.12.23

Gerhard "Ask Me About System Design" Paseman, 2011.12.06

$\endgroup$
9
  • $\begingroup$ @ Gerhard: Shouldn't there be five essentially different forms? In my answer I give three different forms (two of my four matrices differ only in the placement of the non-1 elements). In addition to these three, there is the matrix with three 1s in a row and three 1s in a column, and the matrix with three 1s in a row and two rows each containing a single 1 in different columns. $\endgroup$ Dec 22, 2011 at 12:46
  • $\begingroup$ Indeed Will, there should be five: I conflated two classes when I should not have. I will edit later and include some more remarks. Gerhard "Ask Me About System Design" Paseman, 2011.12.22 $\endgroup$ Dec 23, 2011 at 2:07
  • $\begingroup$ Gerhard, would you elaborate on the derivation of the 1/4 upper bound in the case where the multiset contains four 1s? If you put the four 1s in a 2x2 block, giving determinant D=(a-b)(c-d), it seems to me that you can find values of a, b, c, and d in [-1,1] such that the minimum value of |D| over all permutations of a, b, c, and d is larger than 1/4, but perhaps I'm misunderstanding the argument. By the way, I am now strongly convinced that the lower bound of 0.1859138 for a(3) cannot be improved. $\endgroup$ Dec 23, 2011 at 18:25
  • $\begingroup$ It is a "shoot from the lip" estimate that is likely incorrect, but the idea is as follows. Since there are four ones, there are 5 unknowns distributed in [-1,1), guaranteeing that at least two of them are less than 1/2 distance apart. Although it may be possible to get five arranged so that any two pairs from the five will form a product greater than 1/4, it seemed hard to produce such a case. Anyway, it is clear to me that from the five entries one can get a product less than 1/2, and 1/4 may be likely. Gerhard "Fires From Lip And Hip" Paseman, 2011.12.23 $\endgroup$ Dec 23, 2011 at 20:16
  • $\begingroup$ Even if the 1/4 turns out to be a bad value, for the four ones case I am convinced that a(3)< 1/2, and I hope to encourage someone to develop a cheap upper bound like a(n) < 1 or even a(n) > a(n+1) with the ideas I've suggested. I feel as you do a(3) is not much larger than 9/50. Gerhard "Ask Me About Uneducated Guessing" Paseman, 2011.12.23 $\endgroup$ Dec 23, 2011 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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