On Wednesday 25 May 2005 16:18, Mike Speciner wrote:

If by summetry you mean the fact that all but one of the rows have the same number of 0s as 1s, you can replace 10011011 with 00011011 and have them all have that property. (The cofactor of the changed bit is 0.) You'll note that the columns are not particularly symmetric in this sense.

No, what I meant was the presence of things like 11001100 and 01010101 and 01100110, which have considerably more symmetry to them than just equal numbers of 0s and 1s.

You haven't described your hillclimbing algorithm, but to maximize the determinant while changing a single row, you clearly set each element in the row to 0 if its cofactor is negative and 1 if the cofactor is positive. (If the cofactor is 0, the element doesn't matter.) If you assume that a cofactor is as likely to be positive as negative, then you'd expect roughly the same number of 0s as 1s.

The hillclimbing algorithm was the simplest imaginable: try all possible single-bit changes and choose a random maximal-determinant result; repeat until no further improvement is possible. Your observation about cofactors is astute, though I suspect (with no evidence) that global optima might be more accessible by a hillclimbing approach that takes fewer steps and leaves more open to chance. (But I'd have done the cofactor thing if I'd thought of it.) In another message you mention starting with random matrices and discarding ones with negative determinant; of course you can just transpose two rows if you start with a negative determinant :-). -- g

Oh, here are the matrices for 38 and 39... m{38}: 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 m{39}: 1 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 Mike Speciner wrote:

I just did a quick matlab program to do random matrices (eliminating those with non-positive determinant) and hillclimb by replacing each element (row by row and then column by column) with 0 if its cofactor is - and 1 if its cofactor is +. I've gotten all positive dets from 1 through 40, then 42 44 45 48 and 56. (That's 91 by the way, 7*13)

--ms

Gareth McCaughan wrote:

...

...

Generating a bunch of random boolean 8x8's, I've gotten every determinant from 0 to 32, and 34, 35, 36, 42. 73 different values, when you count the negative ones.

33: 00001111 01011100 11000100 01100001 10010101 10111110 01010110 11011011 40: 11101000 00110110 10001111 01011101 10010001 00011010 01100011 00101001 44: 00101010 10000011 11001000 10011110 11110010 01011011 01100101 10111001 45: 11001011 01110011 10010101 10100110 01010110 00101111 11111100 10011010 48: 11100100 01100011 10000111 01001110 10101010 10111101 11010010 00110110 56: 11001100 01101001 10011011 01010101 01100110 00111100 11110000 10100101

These were found by naive hillclimbing starting from random matrices, which makes it interesting to me how much symmetry there seems to be in the last one's rows. But maybe I'm being taken in by the Strong Law of Small Numbers myself now.

Anyone got a proof that bigger than 56 is impossible? Or a way to rule out (e.g.) 38 or 39?

------------------------------------------------------------------------

function hist = det01(n)

% hist = det01(n)

hist1 = zeros(1,n*n); hist2 = zeros(1,n*n);

for c = 1:10000 m = +(rand(n,n) < .5); d = det(m); if d <= 0 continue; end hist1(d) = hist1(d) + 1; for i = 1:n for j = 1:n d = cof(m,i,j); if d < 0 m(i,j) = 0; elseif d > 0 m(i,j) = 1; else continue; end d = det(m); hist2(d) = hist2(d) + 1; end end end

hist = [hist1;hist2];

function c = cof(m,i,j) c = (-1)^(i+j) * det(m([1:(i-1) (i+1):n],[1:(j-1) (j+1):n])); end

end

------------------------------------------------------------------------

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

function [hist,mats] = det01(n) % [hist,mats] = det01(n) hist1 = zeros(1,n*n); hist2 = zeros(1,n*n); mats = cell(1,n*n); for c = 1:10000 m = +(rand(n,n) < .5); d = det(m); if d <= 0 continue; end if isempty(mats{d}) mats{d} = m; end hist1(d) = hist1(d) + 1; for i = 1:n for j = 1:n d = cof(m,i,j); if d < 0 m(i,j) = 0; elseif d > 0 m(i,j) = 1; else continue; end d = det(m); if isempty(mats{d}) mats{d} = m; end hist2(d) = hist2(d) + 1; end end end hist = [hist1;hist2]; function c = cof(m,i,j) c = (-1)^(i+j) * det(m([1:(i-1) (i+1):n],[1:(j-1) (j+1):n])); end end