1
$\begingroup$

Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product of $i$th row and $j$th row of $M$ is $0$ or else it is $1$ with $0$s on the diagonal (disregarding the inner product of $i$th row with itself).

Take the graph whose adjacency is given by $G$.

  1. How many edges does this graph have?

  2. Is it possible to give its rank over $\mathbb F_2$ and $\mathbb R$?

Improve this question
$\endgroup$
5
  • $\begingroup$ $n=2^d$, right? $\endgroup$
    – Fedor Petrov
    Commented Aug 13, 2019 at 14:05
  • $\begingroup$ True $n = 2^{d}$. $\endgroup$
    – Turbo
    Commented Aug 13, 2019 at 14:06
  • $\begingroup$ Shouldn't the rank of $M$ simply be $d$ (in $\Bbb R$ and $\Bbb F_2$), as the matrix contains the $d\times d$-identitiy matrix as a submatrix? $\endgroup$
    – M. Winter
    Commented Aug 13, 2019 at 14:36
  • $\begingroup$ @M.Winter Don't know since we round. $\endgroup$
    – Turbo
    Commented Aug 13, 2019 at 14:52
  • $\begingroup$ @Turbo Wait, are you asking about the rank of the adjacency matrix or the rank of $M$? $\endgroup$
    – M. Winter
    Commented Aug 13, 2019 at 15:00

1 Answer 1

Reset to default
2
$\begingroup$

Concerning the edges, consider the following:

Let $v\in \smash{\{0,1\}^d}$ be a 0/1-vector with exactly $k$ zeroes. If $v\not=0$, there are exactly $2^k$ 0/1-vectors that have vanishing inner product with $v$. The vector $v=0$ is an exception, as it has zero inner product with itself (this would give a loop otherwise), and so we count only $\smash{2^d-1}$ neighbors for this one. The number of non-edges then is

$$\frac 12 \Big[\sum_{k=0}^d {d\choose k} 2^k-1\Big] = \frac {3^d-1}2.$$

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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