combinatorics

## Primary tabs

# combinatorics

Submitted by anirban_mandal on Thu, 04/29/2010 - 09:04

Forums:

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?

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Versions

(v1) by anirban_mandal 2010-04-29

## Re: combinatorics

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};]