5
$\begingroup$

An $m \times n$ matrix $A$ is called a binary matrix if all entries of $A$ are either $0$ or $1$. Also, a vector $\mathbf{x}$ in $\mathbb{R}^n$ is called a trinary vector if all entries of $\mathbf{x}$ are either $-1$, $0$, or $1$.

I want to prove/disprove the following assertion.

Given an $m \times n$ binary matrix $A$, it is always possible to construct a basis for a null space of $A$ with trinary vectors only.

I played with matlab, and didn't find any counter example at least for comparatively small $m,\, n$. Any idean would be appreciated.

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Here is a counterexample:

\begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}

The lines of this $3\times 4$ matrix being linearly independent, the kernel is of dimension 1. It is generated by the following vector

\begin{bmatrix} -2 \\ -1 \\ 1 \\ 1 \end{bmatrix} .

Therefore there is no trinary vector generating the null space of that binary matrix.

The question of determining which conditions on $A$ imply the existence of a trinary basis seems a very interesting (and non-trivial) task. Any ideas in this direction are welcome...!

$\endgroup$
1
  • $\begingroup$ Here's another formulation: by adding rows/cols of 0's, we may assume that $m=n$. We may then view the matrix as the incidence matrix of a simple directed graph with loops, and you want eigenvectors of this graph with values in $\{0, \pm 1\}$. (That is, assign a weight in $\{0, \pm 1\}$ to each vertex such that the sum of incoming weights at distance $1$ is $0$ for each vertex.) If you assume that the matrix is symmetric and that there are no loops, and weights are in $\{ \pm 1\}$, then this is discussed in this paper: amc-journal.eu/index.php/amc/article/viewFile/1021/982 $\endgroup$
    – Bart Michels
    Apr 24, 2020 at 7:30
0
$\begingroup$

A family of binary matrices for which the answer is positive is presented here, see Proposition 3.4 on page 20. The family of trinary vectors thus obtained define an hyperplane arrangement associated to the permutahedron.

$\endgroup$

You must log in to answer this question.

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