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
    Feb 27 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.