Multiply Then Add, Smallest Possible Integer

[Leroy Quet]

Call a matrix super-robust if every k x k submatrix is non-singular 
(choose any k rows and independently any k columns).  What is the 
largest super-robust square matrix that can be made with integers 1 to 
n?

(Note that allowing 0 doesn't add anything, since any 0 is a 1 x 1 
singular matrix.)

http://www.research.att.com/~njas/sequences/A018805 is an upper bound, 
since with more than that every pair of rows (or columns) will have a 
singular 2 x 2 submatrix.

For n = 1, the maximum is trivially 1.
For n = 2, the following matrix is super-robust:

2 1 1
1 2 1
1 1 2

For n = 3, the upper bound of 7 is not possible.  (Start with 2 rows 
wlog 1 1 1 2 2 3 3 and 1 2 3 1 3 1 2; another row must start 2 1, and 
the next value must both be and not be 3.  Starting with 3 2's or 3 3's 
in each row instead of 3 1's produces the same combinatorial problem.)  
I would be surprised if 5 is not possible, but 6 could go either way.

One can also ask the same question, allowing values -n to n in the 
matrix.  In this case, 2 * A018805(n) is an upper bound.

For n = 1, the maximum of 2 is achievable:

1 1
1 -1

The upper bound for n = 2 is 6; I don't know how close you can get.

In both cases, can the maximum always be obtained with a symmetric 
matrix?

Franklin T. Adams-Watters

________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.