Binary Chess?

Algebra Level 5

How many invertible ("non-singular") 8 × 8 8 \times 8 matrices ("chess boards") are there that contain 9 ones and 55 zeroes?

Inspiration


The answer is 2257920.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Ivan Koswara
Sep 7, 2015

Observe that we cannot have any zero row/column (basic linear algebra; such row would make the determinant zero and hence non-singular). Thus each row/column must have at least one 1 1 ; together with there being only nine 1 1 s, one row/column has exactly two while the rest have exactly one each. Call the row/column with two 1 1 s doubled .

Permuting rows/columns don't change whether a matrix is singular or not, thus we can assume that our doubled row and column are the first row and first column, respectively, and we'll remember to multiply by 8 8 8 \cdot 8 later.

Can their intersection be zero? Suppose so. Then we use two 1 1 s in the first row and two more 1 1 s in the first column. These together occupy three rows and three columns, so there are five rows/columns that are still empty. We also have only five 1 1 s remaining, so they must all go to intersections of these currently empty rows/columns. But now our matrix is singular: the two rows having 1 1 in the first column are exactly identical. (Basic linear algebra again: if a row can be produced as a linear combination of the other rows, the matrix is singular. In this case the linear combination is simply the other identical row, multiplied by one, and the rest of the rows multiplied by zero.)

Thus the intersection is 1 1 . We can now place our 1 1 of the first row and first column arbitrarily (just permute again later), and so we assume they are next to the corner 1 1 , leaving the lower-right 6 × 6 6 \times 6 still empty. We will multiply the number of solutions by 7 7 7 \cdot 7 .

We're left with six 1 1 s, and six empty rows/columns that intersect in the lower-right 6 × 6 6 \times 6 . These six 1 1 s must then go there, but any way putting them that don't repeat a 1 1 in the same row/column is valid. There are 6 ! 6! such ways (the column number of the 1 1 in each row is a permutation of six elements).

Multiplying them all, we have 8 8 7 7 6 ! = 56 8 ! = 2257920 8 \cdot 8 \cdot 7 \cdot 7 \cdot 6! = 56 \cdot 8! = \boxed{2257920} .

Mohamed Aly
Sep 6, 2015

Consider the main diagonal are all ones and the remaining one will have (64-8=56) places to land in and then shuffle all columns to 8p8 of methods =56*8!

Great! That is the basic idea! A "devil's advocate" might be worried about an over-count: How do we know that, after the shuffling, we don't end up with the same matrix even if we place the "9th one" in different entries? Also, how do you know that your process generates all matrices of the required form?

Otto Bretscher - 5 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...