[superprismatic]

How many N×N matrices are there which satisfy the following?

1. All entries are non-negative integers

2. Every row and every column sums to 3

3. There are no more than two non-zero entries in any row and any column.

Find the number of N×N matrices satisfying the conditions as a function of N.

Edited September 6, 2011 by superprismatic
: for clarification

[bonanova]

Several.

N=1:

3

N=2.

1 2

2 1

And its symmetrical equivalents.

N=3.

1 2 0

2 0 1

0 1 2

And its symmetrical equivalents.

N=4.

1 2 0 0

0 1 2 0

0 0 1 2

2 0 0 1

I guess you could keep going on like that..

[CaptainEd]

3 0

0 3

2 1 0

0 2 1

1 0 2

3 0 0

0 3 0

0 0 3

2 1 0 0

0 2 1 0

0 0 2 1

1 0 0 2

2 0 1 0

0 2 0 1

1 0 2 0

0 1 0 2

Edited September 6, 2011 by CaptainEd

[bonanova]

Some of those have more than 2 non-zero elements per row and column.

But I think there is no limit, based on the model of those that don't.

[CaptainEd]

Yes, once I learned to read English, I saw and removed the ones with 3 1's per row. But, it does seem that you could make N as large as you want with a 2 and a 1 in each row, doesn't it? (Or even a single 3). Maybe I still don't understand the OP.

[bonanova]

I think so.

[superprismatic]

Yes, once I learned to read English, I saw and removed the ones with 3 1's per row. But, it does seem that you could make N as large as you want with a 2 and a 1 in each row, doesn't it? (Or even a single 3). Maybe I still don't understand the OP.

Sorry, I made a clarification on the OP. What I'm looking for is the number of N×N matrices satisfying the conditions as a function of N.

[EventHorizon]

(N!)²

I looked at a number of approaches to the problem, but it turned out to be much simpler than I initially thought (assuming I'm correct in my thinking).

First, take the identity matrix and scramble it while keeping a 1 in each row and column. There are N! of these since it is equivalent to choosing the column for the top 1, then choosing from the remaining columns for the second, etc.

Second, take a matrix with 2's along the diagonal and zeros elsewhere (e.g., 2I, where I is the identity matrix) and do the same thing. Again N!

Now add element-wise each possibility of the first scramble to each possibility for the second, and you get (N!)² possibilities.

And just because I haven't written any proofs recently, here's an attempt. Let me know if I mess up somewhere.

Do all these satisfy the constraints? (my set is a subset of the solution set)

1. All entries are non-negative integers

The element wise addition will only result in 0's to 3's

2. Every row and every column sums to 3

Element-wise adding a matrix that had every row/column add to 1 to one that every row/column added to 2 = a matrix with every row/column adding to 3.

3. There are no more than two non-zero entries in any row and any column.

Similar reasoning to 2. Since I added element-wise two matrices that had at 1 non-zero element in each row/column, you cannot have an element-wise sum with more than two non-zero elements in a given row/column.

Does this method miss any? (the solution set is a subset of my set)

Assume I miss matrix M.

Deconstruct it into two matrices M₁ and M₂ by the following:

-If there is a 1 in M, put a 1 in the corresponding position in M₁

-If there is a 2 in M, put a 2 in the corresponding position in M₂

-If there is a 3 in M, put a 1 in the corresponding position in M₁ and a 2 in the corresponding position in M₂

There will be a 1 in each row/column in M₁ since M must have a 3 or both a 1 and a 2 in each row/column since there can only be at most two non-zero elements that sum to 3.

This means M₁ should have exactly one 1 in each column and row and zeros elsewhere, and similarly for M₂ but with 2's.

Therefore M₁ should have been included in the scrambling of the identity matrix, and M₂ should have been included in the scrambling of the 2I matrix, so my method shouldn't have missed it and we reach a contradiction.

Since my set is a subset of the solution set, and the solution set is a subset of my set, they must be the same set.

[superprismatic]

(N!)²

I looked at a number of approaches to the problem, but it turned out to be much simpler than I initially thought (assuming I'm correct in my thinking).

First, take the identity matrix and scramble it while keeping a 1 in each row and column. There are N! of these since it is equivalent to choosing the column for the top 1, then choosing from the remaining columns for the second, etc.

Second, take a matrix with 2's along the diagonal and zeros elsewhere (e.g., 2I, where I is the identity matrix) and do the same thing. Again N!

Now add element-wise each possibility of the first scramble to each possibility for the second, and you get (N!)² possibilities.

And just because I haven't written any proofs recently, here's an attempt. Let me know if I mess up somewhere.

Do all these satisfy the constraints? (my set is a subset of the solution set)

1. All entries are non-negative integers

The element wise addition will only result in 0's to 3's

2. Every row and every column sums to 3

Element-wise adding a matrix that had every row/column add to 1 to one that every row/column added to 2 = a matrix with every row/column adding to 3.

3. There are no more than two non-zero entries in any row and any column.

Similar reasoning to 2. Since I added element-wise two matrices that had at 1 non-zero element in each row/column, you cannot have an element-wise sum with more than two non-zero elements in a given row/column.

Does this method miss any? (the solution set is a subset of my set)

Assume I miss matrix M.

Deconstruct it into two matrices M₁ and M₂ by the following:

-If there is a 1 in M, put a 1 in the corresponding position in M₁

-If there is a 2 in M, put a 2 in the corresponding position in M₂

-If there is a 3 in M, put a 1 in the corresponding position in M₁ and a 2 in the corresponding position in M₂

There will be a 1 in each row/column in M₁ since M must have a 3 or both a 1 and a 2 in each row/column since there can only be at most two non-zero elements that sum to 3.

This means M₁ should have exactly one 1 in each column and row and zeros elsewhere, and similarly for M₂ but with 2's.

Therefore M₁ should have been included in the scrambling of the identity matrix, and M₂ should have been included in the scrambling of the 2I matrix, so my method shouldn't have missed it and we reach a contradiction.

Since my set is a subset of the solution set, and the solution set is a subset of my set, they must be the same set.

That is a very clear proof of the correct function. Nice!

[bonanova]

Bravo EH.

[bushindo]

(N!)²

I looked at a number of approaches to the problem, but it turned out to be much simpler than I initially thought (assuming I'm correct in my thinking).

First, take the identity matrix and scramble it while keeping a 1 in each row and column. There are N! of these since it is equivalent to choosing the column for the top 1, then choosing from the remaining columns for the second, etc.

Second, take a matrix with 2's along the diagonal and zeros elsewhere (e.g., 2I, where I is the identity matrix) and do the same thing. Again N!

Now add element-wise each possibility of the first scramble to each possibility for the second, and you get (N!)² possibilities.

And just because I haven't written any proofs recently, here's an attempt. Let me know if I mess up somewhere.

Do all these satisfy the constraints? (my set is a subset of the solution set)

1. All entries are non-negative integers

The element wise addition will only result in 0's to 3's

2. Every row and every column sums to 3

Element-wise adding a matrix that had every row/column add to 1 to one that every row/column added to 2 = a matrix with every row/column adding to 3.

3. There are no more than two non-zero entries in any row and any column.

Similar reasoning to 2. Since I added element-wise two matrices that had at 1 non-zero element in each row/column, you cannot have an element-wise sum with more than two non-zero elements in a given row/column.

Does this method miss any? (the solution set is a subset of my set)

Assume I miss matrix M.

Deconstruct it into two matrices M₁ and M₂ by the following:

-If there is a 1 in M, put a 1 in the corresponding position in M₁

-If there is a 2 in M, put a 2 in the corresponding position in M₂

-If there is a 3 in M, put a 1 in the corresponding position in M₁ and a 2 in the corresponding position in M₂

There will be a 1 in each row/column in M₁ since M must have a 3 or both a 1 and a 2 in each row/column since there can only be at most two non-zero elements that sum to 3.

This means M₁ should have exactly one 1 in each column and row and zeros elsewhere, and similarly for M₂ but with 2's.

Therefore M₁ should have been included in the scrambling of the identity matrix, and M₂ should have been included in the scrambling of the 2I matrix, so my method shouldn't have missed it and we reach a contradiction.

Since my set is a subset of the solution set, and the solution set is a subset of my set, they must be the same set.

Clear and elegant as well. Good job!

[CaptainEd]

I am boggled both by the interestingness of the problem and the clarity of the solution. Way to go!