3
$\begingroup$

Given a positive integer $n$. For any symmetric $n\times n$ matrix $M$, write $M_{ik}$ for the $(i,k)$ entry, $M_k$ for the unordered list (multiset) of entries in row $k$, and $S(M)$ for the unordered list (multiset) of all pairs $(M_k,M_{kk})$. (This is the corrected definition from July 22, 2022, after having read the discussion below.)

(i) For which $n$ does $S(M)$ determine $M$ up to a symmetric permutation (i.e., $P^TMP$ where $P$ is a permutation matrix)?

(ii) For the other $n$, what is the structure of the matrices $M$ that cannot be reconstructed up to a symmetric permutation?

Improve this question
$\endgroup$
6
  • $\begingroup$ By symmetric permutation do you mean PMP for a permutation matrix P? $\endgroup$
    – Chris Ramsey
    Commented Jul 20, 2022 at 23:00
  • $\begingroup$ @ChrisRamsey I'm pretty sure symmetric permutation means $P^TMP$, which preserves the symmetry. But I don't understand the question if "set" is taken literally. $\endgroup$
    – Brendan McKay
    Commented Jul 21, 2022 at 0:23
  • $\begingroup$ @BrendanMcKay Ha, of course. I think the idea is $S(M) = \{\{1,2\},\{1,3\}\}$ can only come from the symmetric matrix $\left[\begin{matrix} 2 & 1 \\ 1 & 3\end{matrix}\right]$ and its symmetric permutation (interchanging the 2 and 3). $\endgroup$
    – Chris Ramsey
    Commented Jul 21, 2022 at 1:49
  • 2
    $\begingroup$ @ChrisRamsey Right, but $\pmatrix{0&1\\1&0}$ and $\pmatrix{1&0\\0&1}$ both have $S(M)=\{0,1\}$ if "set" means "set". Even if "multiset" is the intention, these are both the same. I suspect Arnold has something else in mind and he should expain more. $\endgroup$
    – Brendan McKay
    Commented Jul 21, 2022 at 2:20
  • $\begingroup$ neat question; do I interpret this correctly: we have an unordered list of the $n^2$ elements of the $n\times n$ symmetric matrix $M$, and we know which elements are in which row, but we don't know the order in which they appear in each row; can we reconstruct $M$, up to a symmetric permutation $P^\top MP$ ? $\endgroup$
    – Carlo Beenakker
    Commented Jul 21, 2022 at 8:52

1 Answer 1

Reset to default
2
$\begingroup$

The meaning of the question is unclear due to the word "set". As Carlo proposed in a comment, I'll take it that we have an unordered list of $n$ unordered lists of $n$ elements, and we want to identify the symmetric matrices for which those $n$ lists correspond to the rows up to permutation.

Clearly this is possible for $n=1$. For $n\ge 2$, it is impossible in general, as indicated by this example (where $M$ is any symmetric matrix). $$ \pmatrix{0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & M} \qquad \pmatrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & M} $$ The two matrices are not equivalent under simultaneous row and column permutation since they have different diagonal elements.

Note that this counterexample works even if the rows are given as ordered lists.

Now let's consider the case that all the matrix entries are different, up to the constraints of symmetry. Now the equivalence class of the matrix can always be reconstructed. First, the diagonal entries are those appearing in only one row; place them in arbitrary order down the diagonal, say $d_1,\ldots,d_n$. Now the other entries can be identified: for $j\ne k$ the $(j,k)$ entry is the unique value that is both in the same row as $d_j$ and in the same row as $d_k$.

In the new formulation, diagonal elements are identified. This does not help for $n\ge 5$. Take two non-isomorphic simple graphs with the same degree sequence. The simplest example is a path of 4 edges, versus a triangle plus an isolated edge. These both give 2 of $\{\!\{ \mathbf{0},1,0,0,0\}\!\}$ and 3 of $\{\!\{ \mathbf{0},1,1,0,0\}\!\}$, where I wrote the diagonal element bold.

For larger sizes, use two non-isomorphic 2-regular graphs; for example , for $n=6$, a 6-cycle and two triangles both give 6 of $\{\!\{ \mathbf{0},1,1,0,0,0\}\!\}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for having first posed a wrong problem. I had forgotten to specify that the diagonal elements should remain diagonal; see the new formulation. - For a case of (ii), if one exists at all, one needs to have many pairs of equal entries. I settled $n\le4$ by brute force, but my patience didn't last to settle the next case. These attempts suggested to me no promising strategy for the general case. Thus I concluded that the problem is nontrivial and decided to post it here. $\endgroup$
    – Arnold Neumaier
    Commented Jul 22, 2022 at 9:14
  • $\begingroup$ Please look at my followup question mathoverflow.net/q/429381/56920 $\endgroup$
    – Arnold Neumaier
    Commented Aug 31, 2022 at 15:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .