Properties of a Matrix With Unit Row and Column Sums

Linear Algebra · Medium · Free problem

You are handed a real matrix $M$ in which every row sums to

$ and every column also sums to
$.

Answer the following:

  1. Must $M$ be square?
  1. Is $M$ necessarily invertible, or necessarily singular?
  1. Can there exist such an $M$ with $M^2 = 0$?

Hints

  1. Sum all the entries of $M$ in two different ways to compare the number of rows and columns.
  2. Look for an obvious eigenvector. What does $M$ do to the all-ones vector $\mathbf{1}$?
  3. A matrix with $M^2 = 0$ must be nilpotent, so all its eigenvalues are $0$. Is that compatible with the eigenvalue you just found?

Worked Solution

How to Think About It: A matrix whose rows and columns each sum to

$ (with nonnegative entries this is called doubly stochastic, but the row/column-sum facts hold for any real entries) carries a lot of hidden structure. Before grinding algebra, look for an eigenvector you already know and a conserved quantity (the total sum of all entries) that pins down the shape.

Part 1 -- Square: Let $M$ be $m \times n$. Sum every entry two ways. Summing the $m$ row-sums gives $m \cdot 1 = m$. Summing the $n$ column-sums gives $n \cdot 1 = n$. Both equal the grand total of all entries, so $m = n$. The matrix must be square.

Part 2 -- Invertibility is not forced either way: It can be either. The identity $I$ has unit row and column sums and is invertible. The

\times 2$ matrix with all entries
/2$ has unit row and column sums but is rank
$, hence singular. So neither invertibility nor singularity is guaranteed.

Part 3 -- Can $M^2 = 0$? No. The all-ones vector $\mathbf{1}$ satisfies $M\mathbf{1} = \mathbf{1}$ because each row sums to

$. So
$ is an eigenvalue of $M$ with eigenvector $\mathbf{1}$. If $M^2 = 0$ then $M$ is nilpotent and every eigenvalue must be $0$, contradicting the eigenvalue
$. Hence $M^2 = 0$ is impossible. (Equivalently, $M^2$ again has all row and column sums equal to
$, so its entries cannot all be zero.)

Answer: $M$ must be square; it may be invertible or singular; and $M^2 = 0$ is impossible because

$ is always an eigenvalue.

Intuition

The all-ones vector is the workhorse here. Unit row sums mean $M\mathbf{1} = \mathbf{1}$, so

$ is locked in as an eigenvalue, and unit column sums mean $\mathbf{1}^{\top} M = \mathbf{1}^{\top}$. Any time you see a stochastic-like constraint, your first move should be to test the constant vector -- it usually is an eigenvector, and that single fact answers most follow-ups. The common trap on the last part is to reach for the Cayley-Hamilton theorem or characteristic polynomials; the eigenvalue argument is far cleaner. This structure is exactly why Markov transition matrices (row-stochastic) and doubly stochastic matrices never collapse the constant direction -- the stationary or uniform distribution is preserved forever.

Open the full interactive solver →