1
$\begingroup$

We are considering the following problem:

Given an integer $n$ and a sequence of integers $r_i,\ 1\le i\le n$, with $0\le r_i\le n-1$ does there exists a symmetric matrix $A$ such that the diagonal elements of $A$ are $0$'s, the off-diagonal elements are only $-1$ and $1$ and for each $i$ there are exactly $r_i$ $1$'s on the $i$-th row of $A$? How do we construct such a matrix? How do we construct all such matrices (up to some equivalence relation).

For example, if $n$ is even and half of $r_i$ are equal to $n$, the other half to $n-1$. How do we construct such matrices? What about the case when $\{r_i\}_{i=1}^n$ is a constant sequence? When such a matrix exists?

The problem is related to the existence of certain codes with given distances between the codewords.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Replace each $-1$ with $0$. Then the matrix you look for is the adjacency matrix of a graph with a given degree sequence $r_1, r_2, \dots$. Reconstruction of such a graph (and its adjacency matrix) is known as the graph realization problem. E.g., see Wikipedia or this webpage for additional details and solutions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The linked proof of the correctness of the Havel-Hakimi algorithm also seems to imply that any two realizations can be obtained from each other by a sequence of replacements of the following form: Pick 4 vertices $A,B,C,D$ so that there are edges $AB$ and $CD$, but no edges $AC$ and $BD$. Then replace the edges $AB$ and $CD$ by $AC$ and $BD$. $\endgroup$
    – HenrikRüping
    Commented Feb 27, 2023 at 16:03

You must log in to answer this question.

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