Which matrices give the same probability mass function

In a previous question I asked the following.

Consider a fixed (non-random) $3$ by $n$ matrix $M$ whose elements are chosen from $\{-1,1\}$. What is the probability mass function of $Mx$ when $x$ is a random vector with elements chosen independently and uniformly at random from $\{-1,1\}$?

A very nice answer has been given by Justpassingby as follows. First we make the first row of $M$ all $1$s by flipping columns (that is multiplying them by $-1$). There are now $2^2=4$ different possible types of column and the number each type is denoted by the variable $w_i$.

\eqalign{ P\left[Mx=\left( \begin{matrix}k\\ l\\ m\\ \end{matrix} \right)\right] &=2^{-n}\sum_t{w_1 \choose (w_1+t)/2}{w_2 \choose (w_2+\frac{k+m}2-t)/2}{w_3 \choose (w_3+\frac{k+l}2-t)/2}{w_4 \choose (w_4+t-\frac{l+m}2)/2} }

The range of the summation index $t$ is in principle that of $c_1,$ i.e., the set $\{-w_1,-w_1+2,\ldots,w_1-2,w_1\}$ but in practice many of the terms will be zero because of restrictions on the other $c_i.$

Now consider an $n$ by $n$ matrix where all the corresponding $w_i$ terms are either $1$ or $0$. That is, after changing the first row to be all $1$ by flipping columns, all the columns are distinct.

What does an extension of the formula above to $n$ by $n$ matrices with this new restriction tell us about which $n$ by $n$ matrices have exactly the same pmf?

• If the pmf is the same then the components of $Mx$ have to have the same covariance matrix. I think that this implies that the two matrices have to have the same inner product of rows $i$ and $j$ for every $1\leq i<j\leq n.$ Conjecture: this condition is also sufficient, i.e., the pmf of $Mx$ is completely determined by the numbers $a_{ij}=\sum_{k=1}^nm_{ik}m_{jk}.$ – Justpassingby Jan 8 '16 at 9:39
• @Justpassingby We know that all non-singular $n$ by $n$ $\{-1,1\}$-matrices have the same pmf but I don't think all non-singular matrices give the same covariance matrix do they? – dorothy Jan 8 '16 at 9:40
• How do we know that all nonsingular such matrices have the same pmf? – Justpassingby Jan 8 '16 at 9:43
• @Justpassingby Hmm.. maybe I am being sloppy. If $M$ is non-singular then every vector $x$ gets mapped to a different product $Mx$. So the probabilities of the outcomes that can occur are always $2^{-n}$ exactly. I suppose that what those outcomes actually are may differ however. – dorothy Jan 8 '16 at 9:45

Update: this answer is no longer valid because the lemma, which I posted as a separate question here, turns out to be false. I will either delete it or modify it - generally a doubtful action for an accepted answer, but it cannot stand in its current form.

Let $D$ be the $n$-dimensional hypercube $$D=\left\{(x_1,\ldots,x_n)|\forall i\in\{1,\ldots,n\}\,x_i\in[-1,1]\right\}$$ Let $V$ be the set of its vertices $$V=\left\{(x_1,\ldots,x_n)|\forall i\in\{1,\ldots,n\}\,x_i\in\{-1,1\}\right\}$$ I think that I can answer the question modulo the following lemma.

Lemma.

If $K$ and $L$ are linearly independent subsets of $V$ and $f:K\to L$ is an isometric bijection, then there exists a global symmetry $\sigma$ of $D$ that restricts to $f$ on $K.$

Now we are ready to consider the question.

If two matrices give the same probability mass function (pmf) then they should give the same covariances. The covariance matrix of $y$ is

$$E[y.y^T]=M.M^T$$

so the matrices should have the same rank (the number of nonzero eigenvalues of $M.M^T$ counting multiplicities).

The problem is stated for $n\times n$ matrices but that is not essentially simpler than general $r\times n$ matrices. If we have an $n\times n$ matrix of rank $k$ then we can write $n-k$ rows as linear combinations of the other $k$ rows; these linear combinations follow from the covariance matrix so our only hope for two different matrices with the same distribution is by looking at the $k$ linearly independent rows. Therefore from now on we consider rectangular $r\times n$ matrices ($r\leq n$) of full rank $r.$

The $r$ rows of $M$ form a linearly independent subset of $V.$ If we have two different matrices with the same pmf then these linearly independent subsets are isometric (because the covariance matrix fixes their distances). By the lemma, there exists a symmetry $\sigma$ of the $n$-hypercube $D$ that maps the rows of the two matrices to each other (in the correct order, we are not allowing permutations of rows because this changes the pmf). But the symmetries of $D$ are generated by reflections in one coordinate (flipping the sign of a column of $M$) and permutations of coordinates (changing the order of columns).

This means that two matrices of the same size give the same pmf if and only if they can be transformed into each other by flipping column signs and exchanging columns.

• Thank you for this! Of course, when this is solved I have another follow up :) I am not entirely sure of the correct terminology but it would also be really interesting to know which matrices have exactly the same (multi)-set of probabilities in their probability mass function. This could potentially be quite different from having exactly the same pmf as we discussed before. What's the proper way of asking this? – dorothy Jan 8 '16 at 17:01
• That problem sounds 'dirtier' than merely permuting the $y_i$ components... do you have a specific application in mind? – Justpassingby Jan 8 '16 at 18:37
• Ultimately I would like to understand how to estimate or give upper bounds for $P(Mx = My)$ for random $x$ and $y$ and $r$ by $n$ matrix $M$. I am happy to assume that all the rows of $M$ are orthogonal and that $r$ and $n$ are large if that makes it easier. – dorothy Jan 8 '16 at 19:06
• With $x$ and $y$ each made up of $n$ independent $\{-1,+1\}$ variables and $M$ a given matrix with deterministic $\{-1,+1\}$ entries, right? – Justpassingby Jan 8 '16 at 19:15
• Yes that is it exactly. – dorothy Jan 8 '16 at 20:03