Operations on a matrix

Maxim Bogdan

Consider a matrix whose entries are integers. Adding a same integer to all entries on a same row, or on a same column, is called an operation. It is given that, for infinitely many positive integers $n,$ one can obtain, through a finite number of operations, a matrix having all entries divisible by $n.$

Prove that, through a finite number of operations, one can obtain the null matrix.

Marius Cavachi

**Posted:** Sun May 24, 2009 1:19 am

_________________

Maxim Bogdan

Jumbler · Riemann Hypothesis Offline Joined: 30 Aug 2006 Posts: 319

Anybody can solve this?

**Posted:** Fri Nov 06, 2009 1:29 pm

kevinatcausa · Riemann Hypothesis Offline Joined: 23 Jul 2004 Posts: 264

Here's something I think works:

Let $a_{ij}$ denote the entry of our matrix in row $i$ and column $j$ . Note that for any two rows $(i, k)$ and any two columns $(j, l)$ , the expression $a_{ij}+a_{kl} - a_{il} - a_{kj}$ is left unchanged by any operation. On the other hand, if all the entries are divisible by $n$ , this expression must also be divisible by $n$ . It follows that for every pair of rows and columns this expression is in our original matrix already divisible by infinitely many $n$ ...in other words, it must always be equal to $0$ .

Applying this observation with $k$ and $l$ equal to $1$ , we see that for every $i>1$ and $j>1$ we must have
$a_{ij}=a_{i1}+a_{1j}-a_{11} : =f(i)+g(j),$
where $f(i)$ is defined to equal $a_{i1}-a_{11}$ and $g(j)$ is defined to equal $a_{1j}$ . By inspection, we see that this relation also holds when either $i$ or $j$ is equal to $1$ .

We can therefore add $-f(i)$ to each row and $-g(j)$ to each column to obtain the null matrix.

**Posted:** Fri Nov 06, 2009 2:02 pm

Johan Gunardi · Yang-Mills Theory Offline Joined: 01 Jun 2008 Posts: 713

Assume that after a finite number of operation, row i is added by r_i and column j is added by r_j, such that all entries are divisible by n. Consider everything in modulo n. Take note at the entries a_1,1, a_i,1, a_1,j, a_i,j. We have a_1,1+c_1+r_1=a_i,1+c_i+r_1=a_1,j+c_1+r_j=a_i,j+c_i+r_j in modulo n. From this, we get a_i,j=a_1,1-a_i,1-a_1,j mod n. Since this holds for infinitely many modulo, so the equation must hold. The conclusion follows easily.

**Posted:** Mon Nov 09, 2009 7:46 am

kevinatcausa · Riemann Hypothesis Offline Joined: 23 Jul 2004 Posts: 264

As an interesting sidenote, suppose we were to try and apply the same argument to a three-dimensional array of integers, where the legal operations are adding an integer to all the entries along any hyperplanes where one of the variables is constant. The analogue to the identity above is
$a_{i_1, j_1, k_1}-a_{i_2, j_1, k_1}-a_{i_1, j_2, k_1}-a_{i_1, j_1, k_2}+a_{i_2, j_2, k_1}+a_{i_2, j_1, k_2}+a_{i_1, j_2, k_2}...$
but this is no longer enough to establish the relation $a_{i,j,k}=f(i)+g(j)+h(k)$ -- the entries could satisfy a quadratic relationship instead of a linear one (e.g. $a_{i,j,k}=(i+j)^2+2k^2-3(i+k)^2$ ). In a sense this is because by moving up a dimension we're looking at a discrete analogue of the third derivative instead of the second derivative, and quadratic forms have third derivative equal to zero. So the arguments given above break down for this new problem.

Does the problem statement still hold in $3$ (or $m$ ) dimensions?

**Posted:** Mon Nov 09, 2009 12:35 pm