9
$\begingroup$

Let $n\in\mathbb N$ and an arbitrary binary matrix $M\in\{0,1\}^{n\times n}$ of full rank be given such that the last row of $M$ equals $(1,1,\ldots,1)$. The following problem arose from a research question I have been working on recently.

The core mechanic of the "game" is about taking any two rows $m_j,m_k$ of $M$ and partitioning them into $\min\{m_j,m_k\},\max\{m_j,m_k\}$ where $\min,\max$ operate entrywise. Just as an example to make things clear, if $m_j=\begin{pmatrix}1&0&1&0 \end{pmatrix}$ and $m_k=\begin{pmatrix} 1&1&0&0 \end{pmatrix}$ then $$ \min\{m_j,m_k\}=\begin{pmatrix}1&0&0&0\end{pmatrix}\qquad \max\{m_j,m_k\}=\begin{pmatrix} 1&1&1&0\end{pmatrix} $$ and, obviously, $m_j+m_k=\min\{m_j,m_k\}+\max\{m_j,m_k\}$. Starting from $M_0:=M$ there are three possible scenarios:

  1. Neither $\min\{m_j,m_k\}$ nor $\max\{m_j,m_k\}$ are a row of $M_0$. Then do nothing.
  2. Either $\min\{m_j,m_k\}$ or $\max\{m_j,m_k\}$ are a row of $M_0$ (but not both). Then extend $M$ by the other row vector. (Here we use the convention that the $0$ vector is a row of $M$ so if $\min\{m_j,m_k\}=0$ then extend $M_0$ by $\max\{m_j,m_k\}$ to get a new matrix $M_1$.)
  3. Both $\min\{m_j,m_k\}$ and $\max\{m_j,m_k\}$ are a row of $M_0$. Then do nothing.

Repeat this process (where $M_0$ becomes $M_l$ and $M_1$ becomes $M_{l+1}$ in step $l\in\mathbb N_0$) until for every two rows of $M_l$ scenario 2 does not occur anymore, i.e. it is maximal in this sense and no other row is added via this scheme (then denoted by $M_\text{max}$). Now the "game" ends with a victory if there exist rows $m_{i_1},\ldots,m_{i_n}$ of $M_\text{max}$ such that $$ \begin{pmatrix}m_{i_1}\\\vdots\\m_{i_n}\end{pmatrix}=\begin{pmatrix} 1&0&\cdots&0\\ \vdots&\ddots&\ddots&\vdots\\ \vdots&&\ddots&0\\ 1&\cdots&\cdots&1 \end{pmatrix}\underline{\sigma}\tag{1} $$ for some permutation $\sigma\in S_n$ (where $\underline{\sigma}$ is the corresponding permutation matrix. This is equivalent to saying that $m_{i_{l+1}}$ arises from $m_{i_l}$ by turning a $0$ into a $1$ for all $l=1,\ldots,n-1$.

This concept should become a lot clearer again by considering an example.

Example 1. Let $$ M=M_0=\begin{pmatrix} 1&0&0&0\\ 0&1&1&0\\ 1&0&1&1\\ 1&1&1&1 \end{pmatrix}=\begin{pmatrix}m_1\\m_2\\m_3\\m_4\end{pmatrix}\tag{2} $$ which is of full rank so we may start the game using this matrix. Now take for example $m_2$ and $m_3$ so $$ \min\{m_2,m_3\}=\begin{pmatrix} 0&0&1&0\end{pmatrix}\qquad\max\{m_2,m_3\}=\begin{pmatrix} 1&1&1&1\end{pmatrix}\,. $$ Because $\max\{m_2,m_3\}$ is a row of $M$ but $\min\{m_2,m_3\}$ is not, apply Step 2 to get $$ M_1=\begin{pmatrix} 1&0&0&0\\ 0&0&1&0\\ 0&1&1&0\\ 1&0&1&1\\ 1&1&1&1 \end{pmatrix} $$ Doing the same for $m_1$ and (now) $m_3$ yields $\max\{m_1,m_3\}=(1\ 1\ 1\ 0)$ and $\min\{m_1,m_3\}=(0\ 0\ 0\ 0)$. By our convention this again is Scenario 2 so we extend $M_1$ by $(1\ 1\ 1\ 0)$ to get $$M_2=\begin{pmatrix} 1&0&0&0\\ 0&0&1&0\\ 0&1&1&0\\ 1&0&1&1\\ 1&1&1&0\\ 1&1&1&1 \end{pmatrix}$$ Once more for $m_4,m_5$ and we arrive at $$ M_3=\begin{pmatrix} 1&0&0&0\\ 0&0&1&0\\ 0&1&1&0\\ 1&0&1&0\\ 1&0&1&1\\ 1&1&1&0\\ 1&1&1&1 \end{pmatrix}=M_\text{max}\,. $$ One readily verifies that for any two rows of $M_3$ the above rule ends in Scenario 3 (so in particular not in Scenario 2, nothing new can be generated anymore) which shows maximality. The submatrices of $M_\text{max}$ which satisfy the winning condition read $$ \begin{pmatrix} 1&0&0&0\\ 1&0&1&0\\ 1&0&1&1\\ 1&1&1&1 \end{pmatrix}, \begin{pmatrix} 1&0&0&0\\ 1&0&1&0\\ 1&1&1&0\\ 1&1&1&1 \end{pmatrix}, \begin{pmatrix} 0&0&1&0\\ 1&0&1&0\\ 1&0&1&1\\ 1&1&1&1 \end{pmatrix}, \begin{pmatrix} 0&0&1&0\\ 1&0&1&0\\ 1&1&1&0\\ 1&1&1&1 \end{pmatrix}, \begin{pmatrix} 0&0&1&0\\ 0&1&1&0\\ 1&1&1&0\\ 1&1&1&1 \end{pmatrix}\tag{3} $$

One can also reformulate the problem in terms of directed graphs, which may (or may not) be a good alternative approach here but it certainly visualizes this problem in a nice way. Turn row vectors $\{m_1,\ldots,m_l\}$ into vertices $\{v_1,\ldots,v_l\}$ and draw an arrow from $v_j$ to $v_k$ whenever $v_k-v_j$ is a standard basis vector (i.e. $v_k-v_j$ consists of $n-1$ zeros and one $1$). Again by convention, $(0\ \ldots\ 0)$ is turned into a vertex as well. The victory condition then is met if and only if there exists a path from $(0\ \ldots\ 0)$ to $(1\ \ldots\ 1)$ which is equivalent to $A_\text{max}^n\neq 0$ with $A_\text{max}$ the adjacency matrix of the graph corresponding to $M_\text{max}$.

Example 1 (directed graphs-version). The graph of the original $M$ from (2) is 3 with adjacency matrix $$A_0=\begin{pmatrix} 0&1&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&1\\0&0&0&0&0 \end{pmatrix}\,.$$ Then $M_1$ converts to 2 with adjacency matrix $$A_1=\begin{pmatrix} 0&1&\color{blue}1&0&0&0\\0&0&\color{blue}0&0&0&0\\\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}1&\color{blue}0&\color{blue}0\\0&0&\color{blue}0&0&0&0\\0&0&\color{blue}0&0&0&1 \\0&0&\color{blue}0&0&0&0\end{pmatrix}$$ followed by 1 $$A_2=\begin{pmatrix} 0&1&1&0&0&\color{blue}0&0\\ 0&0&0&0&0&\color{blue}0&0\\ 0&0&0&1&0&\color{blue}0&0\\ 0&0&0&0&0&\color{blue}1&0\\ 0&0&0&0&0&\color{blue}0&1\\ \color{blue}0&\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}1\\ 0&0&0&0&0&\color{blue}0&0 \end{pmatrix}$$ and 4 $$ A_3=A_\text{max}=\begin{pmatrix}0&1&1&0&\color{blue}0&0&0&0\\ 0&0&0&0&\color{blue}1&0&0&0\\ 0&0&0&1&\color{blue}1&0&0&0\\ 0&0&0&0&\color{blue}0&0&1&0\\ \color{blue}0&\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}0&\color{blue}1&\color{blue}1&\color{blue}0\\ 0&0&0&0&\color{blue}0&0&0&1\\ 0&0&0&0&\color{blue}0&0&0&1\\ 0&0&0&0&\color{blue}0&0&0&0 \end{pmatrix}\,.$$ The blue numbers are the ones that are added in the corresponding step. Also note that the adjacency matrices of the individual steps are necessarily triangular. Now the victory condition is met if and only if $A_\text{max}^4\neq 0$. Indeed $A_\text{max}^4=5 e_1e_n^T$ so there exist 5 different paths (corresponding to eq.(3)) that lead from $(0\ \ldots\ 0)$ to $(1\ \ldots\ 1)$. Be aware that $A_2^4=e_1e_n^T\neq 0$ becasue there is one path from $\vec 0$ to $\vec 1$ so we already won after the second step.

The whole time I put the word "game" in quotation marks for the following reason:

Conjecture 1. For every $M$ satisfying the above conditions the game ends in a victory, i.e. $M_\text{max}$ contains at least one submatrix of form (1). Equivalently the directed graph corresponding to $M_\text{max}$ contains at least one path leading from from $(0\ \ldots\ 0)$ to $(1\ \ldots\ 1)$, i.e. $A_\text{max}^n\neq 0$.

A useful intermediate step might be the following:

Conjecture 2. Let $M$ satisfying the above conditions be given. For any two rows $m_j,m_k$ of $M_\text{max}$ only scenario 3 can occur.

These conjectures are supported by a plethora of examples I have computed (up to $n=6$) which makes me rather confident that this is true. Two short comments to make here.

  1. The full rank condition on $M$ cannot be waived or replaced by something like "all rows of $M$ have to be pairwise distinct". For this consider $$ M=\begin{pmatrix} 1&1&0\\0&1&1\\1&1&1 \end{pmatrix}=M_\text{max} $$ which does obviously not satisfy the winning condition (although for any two rows, Scenario 3 occurs).
  2. Having one row equal to $(1\ \ldots\ 1)$ is necessary. Consider $$ M=\begin{pmatrix} 1&1&0\\1&0&1\\0&1&1\end{pmatrix}=M_\text{max}\,, $$ cf. also mjacobse's answer.

I am currently lacking ideas on how to approach this problem. Working with the adjacency matrices seems like a possibility, although I neither see how the rank of $M$ is reflected in $A_\text{max}$ nor do I see a general pattern there yet. The only thing I see is that if $M_1,M_2\in\{0,1\}^{n\times n}$ of full rank satisfy $M_1=M_2\underline{\tau}$ for some permutation $\tau\in S_n$ then $M_1$ leads to victory if and only if $M_2$ does---so we can reduce this problem to equivalence classes of initial matrices but this should at best be a simplification, not an idea for a proof. Thank you in advance for any comments and or ideas!

$\endgroup$

1 Answer 1

4
$\begingroup$

I wrote a quick python script to try to bruteforce counter examples. Unfortunately, it quickly found the counter examples

$$ \begin{pmatrix} 0& 1& 1\\ 1& 0& 1\\ 1& 1& 0 \end{pmatrix} $$

if the last row does not have to be only ones and among others

$$ \begin{pmatrix} 1& 0& 1& 0\\ 1& 1& 0& 0\\ 0& 1& 1& 0\\ 1& 1& 1& 1 \end{pmatrix} $$

if it does.

$\endgroup$
3
  • 1
    $\begingroup$ Interesting, the second counterexample loses its effect if one extends the rules to allow sums of more than two rows (related to the inclusion-exclusion principle) because then $1010+1100+0110=2220=2*(1110)+(0000)$ and we get $1110$ as a new row etc. But that is beyond what my current question asks so this works and I learned something. Great job! $\endgroup$ Oct 15, 2019 at 19:37
  • 1
    $\begingroup$ Just curious, in condition 1, if we instead add the two rows to $M$, do you find counterexamples? $\endgroup$
    – vujazzman
    Oct 15, 2019 at 19:38
  • 1
    $\begingroup$ @vujazzman Could not find any in a quick run for matrix dimensions smaller than 10. Would have to put some effort into a more efficient script to do more rigorous testing. However, I would not be surprised if there aren't any counter examples in that case. It feels like pretty much any possible binary row would be in the matrix at some point. $\endgroup$
    – mjacobse
    Oct 15, 2019 at 19:56

You must log in to answer this question.

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