Transforming a matrix A into a zero matrix using finitely many steps.

Question

Let $A$ be a $m\times n$ matrix whose entries are positive integers.

A step consist of transforming the matrix either by multiplying every entry of a row by $2$ or subtracting $1$ from every entry of a column.

My question is can we transform $A$ into the zero matrix in finitely many steps??

Answer 1

Obviously, you can work with each column separately. Let's prove for one column (or for one line since you can transpose your matrix and each of your operations).

1. If your line is $\alpha = (\alpha_1, \dots, \alpha_n) = (1, \dots, 1) = e$ then you just subtract $1$ and get zero string.

2. Suppose $m = \min_i\alpha_i > 1$. Then we can obtain the following line $\alpha \to \alpha - (m-1)e$ which has at least one $1$.

3. Multiply all $\alpha_i = 1$ by $2$.

4. Reiterate steps 2 and 3 until you will get to step 1. Let's prove that finally we will get to step 1. Let's denote $\|\alpha\| = \sum\alpha_i$. If we make step 2 then $\|\alpha\|$ decreases by $(m-1)n \geq n$. If we make step 3 and $\|\alpha\| \neq n$ then $\|\alpha\|$ increases at most by $n-1$. This means that $\|\alpha\|$ decreases every $2$ steps at least by $1$. Then finally we will obtain $\alpha$ with $\|\alpha\| = n$.

Remark. In steps $2-4$ it is easy to see that $\min_i\alpha_i > 0$.

Answer 2

Yes.

1. If you can do this for a 1-column matrix, you can do it for $m$ columns (by zeroing them one at a time), so let's look at the 1-col case.

2. Now your goal is to take a column of numbers and change them, by either doubling individuals or subtracting 1 from all, to identical numbers, after which subtracting 1 from all numbers enough times will do the trick.

Look at the case with two numbers, and write the numbers in binary. Assume, for a start, that they have the same number of $1$s in their binary form. As an example, let's take 3 and 5. (011, 101)

Regardless of the number of bits, I'll call the right-most 1 the "low order bit", so that in 01100, the "low order bit" is the middle one.

If the low order bits are both 1s, we can subtract 1 often enough to change both to zeros:

011
101

010
100

If the low order bits are different, they must be 1 and 0 or 0 and 1. Double whichever number has low order bit 1:

010
100

100
100

and then, when the low order bits agree, subtract 1s.

Each of these operations either reduces the number of 1s or keeps it the same. So the algorithm terminates. Let's look at a more complex example

10110
01101  <- double

10110  <reduce, twice
11010  <reduce, twice

10100  < double
11000

101000 < reduce 8 times
 11000 < reduce 8 times
100000
 10000 < double
100000 < reduce 32 times
100000 < reduce 32 times

Finally, what if the numbers have different numbers of 1 bits? Suppose we have

10100  < 2 "one bits"
11101  < 4 "one bits"

Let's play around a little:

If we shift the top number left one bit (doubling) and subtract 1, we change it to 100111

i.e., we add two "one bits" to it. If we shifted left two bits, we'd add three one-bits. In general, if it has $k$ trailing 0s, then a left-shift by $p$ and subtracting 1 adds $k+p-1$ one-bits to the number.

OK: so the general rule is this: shift either the top or bottom until they have the same numbertrailing zeroes (by multiplying one or the other by 2). Call this number of zeros $k$. Suppose that the top number has $a > 0$ more 1s than does the bottom. (If not, swap the words "top" and "bottom" in what follows). Then shift the bottom number by multiplying by 2 a total of $a$ times, and subtract 1 from both numbers.

Let's see this in action: 10100 < 2 "one bits" 11101 < 4 "one bits" Shift bottom number left to have same number of trailing zeros: 0010100 < 2 "one bits" 1110100 < 4 "one bits" Because bottom number has more bits, shift the TOP number left by $a = 2$ bits: 001010000 < 2 "one bits" 001110100 < 4 "one bits" and subtract 1 from both numbers 001001111 < now has 5 1-bits 001110011 < now has 5 1-bits

The result is two numbers with the same number of 1-bits.

Summary: if you have a column vector with just 2 entries, you can do the following:

1. Do the bit-shifting just described to make the number of 1-bits equal
2. Do the steps described earlier to kill off the 1-bits, one at a time.

What about a vector with more entries? Easy!

1. Apply the technique above to the first two entries, but reduce them only to 1s rather than both to zeros; doing so will involve subtracting 1 from the other entries at various points. Whenever one of these gets down to 1, double it.

2. When you're done, you'll have $(1, 1, a, b, c, \ldots)$.

3. Now proceed to do the same thing to the second and third entries...but whatever you do to the second row, do to the first row as well (so that the first and second numbers remain identical throughout the process, and apply the "multiply by 2" rule of step 1 to the 4th through $n$the entries). When you're done, you'll have $(1,1, 1, p, q, \ldots)$.

4. Do that again, clearing out one entry at a time, until you have $(1,1,1,\ldots, 1)$.

5. subtract 1 from every entry.