Take the 2-minute tour ×

Is there a name associated to rectangular matrices $M \times N$ that have exactly one entry equal to $1$ in each row and $0$ everywhere else?

share|improve this question
Are they in different columns, too? –  Arturo Magidin Mar 4 '11 at 19:09
@Arturo: no, $N$ can be smaller than $M$. If they were in different columns, it would be just a stochastic matrix, right? –  Alessandro Cosentino Mar 4 '11 at 19:12
I don't think they have any special name; if you had, say, a single column of $1$s, it would be a very different kind of matrix as one in which the $1$s are more evenly distributed. Of course, it's a "sparse" matrix, but that's much more general. –  Arturo Magidin Mar 4 '11 at 19:17
@Arturo. thanks anyway. –  Alessandro Cosentino Mar 4 '11 at 19:21

3 Answers 3

Such a matrix is precisely a matrix representation of an arbitrary function from a set of size $M$ to a set of size $N$, in the sense that multiplication by a row vector is a linearized version of evaluating the function.

share|improve this answer
This fits in with the picture of vector spaces over $\mathbb{F}_1$ being (pointed) sets and linear maps being maps of (pointed) sets. –  Zhen Lin Mar 4 '11 at 22:19
basically that's where my matrix comes from. I was asking for a name of such matrices. Thanks anyway. –  Alessandro Cosentino Mar 4 '11 at 22:36

For $M=N$, these are called permutation matrices. (striked according to Moron's comment) Yours are a (admittedly very restricted) special case of matrices with the consecutive ones property, but I'm not sure how much that helps you.

share|improve this answer
Not if they can be in the same column, which is what Arturo's comment was aimed at, I presume. –  Aryabhata Mar 4 '11 at 19:37
You're right, I'm fixing that. –  Anthony Labarre Mar 4 '11 at 19:38

Wikipedia gives: "A right stochastic matrix is a square matrix each of whose rows consists of nonnegative real numbers, with each row summing to 1."

This definition restricts you to square matrices, but in Henryk Minc's book "Permanents" he explicitly considers non-square matrices and is always careful to say "$n$-square doubly stochastic" when he means this.

It fits in with Qiaochu Yuan's answer in that an arbitrary right stochastic matrix gives a 'function' where $M_{ij}$ is the probability that element $i$ in the domain is mapped to element $j$ in the co-domain.

share|improve this answer

Your Answer


