1
$\begingroup$

Let $\mathbf{x}_1$ and $\mathbf{x}_2$ be column vectors with entries belonging to the set $\{0,1\}$. In addition, let $\mathbf{A}$ be the adjacency matrix of an arbitrary graph. I want to find vectors $\mathbf{x}=\mathbf{x}_1\otimes\mathbf{x}_2$ with the most number of ones such that

$$\mathbf{x}^{\mathsf{T}}\mathbf{A}\mathbf{x}=0$$

where $\otimes$ denotes the Kronecker product, and $\{.\}^{\mathsf{T}}$ denotes the matrix transpose.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are the lengths of $x_1$ and $x_2$ fixed? Or can you choose any lengths whose product gives the number of vertices in the graph? For instance, if $A$ is $20\times 20$, can you choose $x_1\in\{0,1\}^{5}$ and $x_2\in\{0,1\}^{4}$ as well as $x_1\in\{0,1\}^{20}$ and $x_2\in\{0,1\}^{1}$? Because it looks like it is always convenient to take $x_2=1 \in \{0,1\}^1$... $\endgroup$
    – Federico Poloni
    Commented Nov 13, 2016 at 10:14
  • $\begingroup$ The length of $\mathbf{x}_1$ and $\mathbf{x}_2$ are fixed. $\endgroup$
    – Math_Y
    Commented Nov 13, 2016 at 10:24

0

Reset to default

You must log in to answer this question.