Fork me on GitHub
Math for the people, by the people.

User login

combinatorics

Primary tabs

combinatorics

What is the number of ways you can fill an order 'n' square matrix with elements +1 or -1 such that the row wise and column wise products are -1?


Nice problem Anirban!
Clue: We shall enumerate all the [;n-1\times n-1;] matrices [;(n\ge 2);] such that when we insert a row and a column, we get a [;n\times n;] matrix such that product of every row and every column is [;-1;]. Suppose we have a matrix [;M(n-1\times n-1);]. We insert a row and column into it so that the row and column meet at [;a_{ij};] of the resultant [;n\times n;] matrix. Suppose, [;M;] had [;k;] and [;h;] number of columns and rows respectively that had the product [;1;]. We can make the product of these rows and columns in the resultant [;n\times n;] become [;-1;], by appropriately placing [;-1;] and [;+1;] in our new row and column. But the element [;a_{ij};] can be filled without a clash iff [;k;] and [;h;] have same pairity.

Therefore, we are left to enumerate the number (say [;N;]) of [;n-1\times n-1;] $\pm 1$ matrices with number of rows whose product is [;1;] has the same pairity as the number of columns whose product is [;1;]. Our answer shall be [;\frac{N}{n^2};]

Subscribe to Comments for "combinatorics"