# Suppose $M$ is an $m \times n$ matrix such that all rows and columns of $M$ sum to $1$. Show that $m=n$

I find this a rather awkward question, from the book "Mathematical Circles" by Fomin, Genkin and Itenberg. The question number is Question number 23 from Chapter 12 ("Invariants"). I was given a hint: use invariants, which I found even more awkward.

There was also a remark : "strange as it may seem, this is an invariants problem". Funny , because I don't know what to expect now!

Suppose $$M$$ is an $$m \times n$$ matrix such that all rows and columns of $$M$$ sum to $$1$$. Show that $$m=n$$.

I have no clue how this is a problem on invariants, let alone how to solve this problem. I'll need hints on why this is the case.

• Note : This question will be edited to reflect the source of the problem for the relief of future visitors. I still can't believe I missed the answer. Jun 27 at 9:30

If $M$ has $m$ rows that sum to $1$, the sum of the matrix is $m$.

If $M$ has $n$ columns that sum to $1$, the sum of the matrix is $n$.

The sum of the matrix is invariant, therefore $m=n$.

• Wow. That's the invariant (I can't shout, but I can't believe I missed this). Sep 6 '16 at 9:29

Hint: What is the sum of all numbers in the matrix?

• OH, SO THAT'S THE INVARIANT! Sep 6 '16 at 9:29

Let $\mathrm A \in \mathbb R^{m \times n}$ have its $m$ rows and $n$ columns sum to $1$. Hence,

$$\underbrace{1_m^T \mathrm A}_{=1_n^T} 1_n = 1_n^T 1_n = n$$

and

$$1_m^T \underbrace{\mathrm A 1_n}_{=1_m} = 1_m^T 1_m = m$$

Thus, $m = n$.

• That's a nice way of putting it, without needing that word "invariants". Thank you. Sep 6 '16 at 9:50

This question has been answered very nicely, but it might be worth noting that a simple yet less elegant, more brutish way of seeing this problem, is to let the first $$(n-1)$$ columns be anything.

Say they're given by $$a_{ij}, \ i \leq m, \ \ j \leq (n-1)$$.

Then the entries of the last column must be $$1 - \sum_{j=1}^{n-1} a_{ij}, \ i \leq m$$.

Since these entries add up to $$1$$, we have $$1 = \sum_{i=1}^{m} (1 - \sum_{j=1}^{n-1} a_{ij}) = m - \sum_{i=1}^{m} \sum_{j=1}^{n-1} a_{ij} = m \ - \sum_{j=1}^{n-1} \sum_{i=1}^{m} a_{ij} = m - \sum_{j=1}^{n-1}1 \\= m -(n-1)$$

And thus we have $$m=n$$.

• Yes, this is also very beautiful, thank you. Sep 25 '19 at 9:05