He would like to get and array where all entries are divisible by 2013.Then how many arrays are possible..?

108 Views Asked by At

Ramesh is given a $2013\times2013$ array of integers between $1$ and $2013$ both inclusive. He is allowed only $2$ operation.

1)Choose a row,subtract $1$ from each entry.

2)Choose a column ,add $1$ to each entry.

He would like to get and array where all integers are divisible by $2013$. Then how many arrays are possible?

2

There are 2 best solutions below

0
On BEST ANSWER

I'll assume that the question is how many $n\times n$ matrices with entries in $R=\Bbb Z/n\Bbb Z$ there exist that can be written as a sum of matrices with either single row of entries$~1$ and zeros elsewhere or a single column of entries$~1$ and zeros elsewhere, for $n=2013$. (By subtracting off that sum, the matrix can then be reduced to the zero matrix over $R$, and "addition is just repeated subtraction".)

If $n$ were a prime number, the answer would be $n^{2n-1}$ by simple linear algebra: the $n$ generating "row-matrices" and the $n$ generating "column matrices" each obviously span a vector space of dimension $n$ over the field$~R$, the two vector spaces of matrices being characterised by equality of all entries along rows respectively along columns. The intersection of these vector subspaces contains all matrices with all entries equal, and has dimension$~1$, so that the sum of the two subspaces is a subspace of dimension $n+n-1=2n-1$, which has $n^{2n-1}$ elements.

Now $n=2013=3\times11\times61$ is not prime, but the answer is still $n^{2n-1}$ in this case. To see this one basically reasons that the sum can be made direct by removing one generating element from one of the generating sets. So let us forbid using the matrix will entries$~1$ in the final row and zeros elsewhere, after all that matrix can be written as the sum of all "column matrices" minus the sum of all other row matrices. I claim that the remaining generators form an $R$-linearly independent set. Consider an $R$-linear combination giving the zero matrix. Since each entry in the final row occurs only in one generating element (a column matrix), the fact that the combination gives the zero matrix implies that that generating element has zero coefficient in the linear combination; this takes care of the column matrices. But a nontrivial $R$-linear combination of row matrices is clearly never zero, so we must have had the trivial linear combination of generators. As a consequence of the independence, all $n^{2n-1}$ possible $R$-linear combinations give distinct results, and by definition those are all the matrices that need to be counted.

1
On

Actually, this is not possible in general. This because the two operations decreases or increases, respectively, the total sum by exactly $2013$ upon application.

Thus if the sum of all elements in the array is, let's say, $2,025,079 = 2013\times 1006 + 1$, then you can never make all the elements divisible by $2013$, since the total sum always will be $1$ off from being divisible by $2013$.

Now, whether or not you can make all but one of the elements divisible by $2013$, or what happens if we assume the sum is divisible by $2013$ are questions too interesting for me to handle at the moment.