A Hadamard product of binary (or ternary) matroids

Question

I would like to know if anyone has studied the following ``Hadamard product" of binary (or ternary) matroids. (There is a notion of Hadamard product of matroids studied e.g. here but I think that one is different.)

Let $M,N$ be simple binary matroids of rank $r$ and $s$, respectively, over the same ground set $E$ of size $n$. For binary representations $(x_1,\dots, x_n)$ and $(y_1,\dots, y_n)$ of $M$ and $N$, respectively, define the Hadamard product of $M \circ N$ to be the binary matroid represented by $(x_1 \otimes y_1, \dots, x_n \otimes y_n)$. One can easily show that this is a well-defined matroid product, using the fact all representations of binary matroids are projectively equivalent [Proposition 6.6.5, Matroid Theory, Oxley].

After a little work, one can derive the linearly independent sets in $M \circ N$. Suppose WLOG that $(x_1,\dots, x_r)$ form a basis for $M$. For each $i \in \{1,\dots, r\}$, let

$$\text{Supp}(i)=\{a \in \{1,\dots, n\} | x_a(i) \neq 0\},$$

where $x_a(i)\in \mathbb{F}_2$ is the $i$-th coordinate of $x_a$ in the basis $(x_1,\dots, x_r)$. Then $S \subseteq [n]$ is linearly independent in $M \circ N$ if and only if for all $\emptyset \neq T \subseteq S$, there exists $i \in \{1,\dots, r\}$ such that $\sum_{a \in T} x_a(i) y_a \neq 0$. This inequality is equivalent (over $\mathbb{F}_2$), to saying that the set

$$T \cap \text{Supp}(i)$$ is not Eulerian in $N$, i.e. it cannot be partitioned into circuits in $N$.

As a side note, I would also be very interested in any feedback on the following conjecture, which is the $\mathbb{F}_2$-version of a conjecture I have been thinking about for some time (preprint here).

Conjecture. Let $M_1,\dots, M_m$ be simple binary matroids of rank $r_1,\dots, r_m$, respectively over the same ground set $E$ of size $n$. If $n \leq \sum_{j=1}^m (r_j-1)+1$, then $M_1 \circ \dots \circ M_m$ is disconnected.

I have proven this conjecture when $m=2$; or $m=3$ and $r_3=2$; or $m$ is arbitrary, $r_1\geq 1$ is arbitrary, and $r_2=\dots=r_m=2$.

Answer 1

I hope that below is the proof of Conjecture (for $n\geqslant 2$, for $n=1$ it is false by trivial reasons), but please check carefully.

If $M$, $N$ are matroids on the ground set $E$ which are represented over a field $\mathbb{F}$: $M=\{x_i:i\in E\}$, $N=\{y_i:i\in E\}$ ($x_i$ and $y_i$ are vectors in corresponding vector spaces $X$, $Y$ over $\mathbb{F}$), we define $M\circ N$ as a matroid on the ground set $E$ over $\mathbb{F}$ corresponding to the tensor products $\{x_i\otimes y_i:i\in E\}$.

Conjecture follows immediately from the following two lemmata.

Lemma 1. If $N$ or $M$ is disconnected, then so is $M\circ N$.

Proof. Obvious.

Lemma 2. If $N$, $M$ and $M\circ N$ are connected, then ${\rm rank} (M\circ N)\geqslant {\rm rank}(M)+{\rm rank}(N)-1$.

Proof. We use the ear decomposition of the connected matroid $M\circ N$: $E$ may be represented as a union of circuits $E=C_1\cup C_2\cup \ldots \cup C_m$ so that the sets $E_k:=C_1\cup \ldots \cup C_k$ satisfy $C_k\cap E_{k-1}\ne \emptyset$, ${\rm rank}(E_k)-{\rm rank}(E_{k-1})=|E_k\setminus E_{k-1}|-1$ for all $k=2,\ldots,m$ (hereafter ${\rm rank}$, ${\rm rank}_M$, ${\rm rank}_N$ denote rank functions of $M\circ N$, $M$, $N$ respectively).

For completeness, I prove that it exists. We start with arbitrary circuit $C_1$. Assume that $C_1,\ldots,C_k$ are already constructed. Let $B$ be a base of $E_k$. Choose consequently independent elements $f_1,f_2,\ldots$ in $E\setminus E_k$ until we get ${\rm rank}(B\cup \{f_1,f_2,\ldots,f_r\})<r+|B|$. If this never happens, we get ${\rm rank}(E_k)+{\rm rank}(E\setminus E_k)={\rm rank}(E)$, and $E$ is disconnected. So sometimes it happens. The set $B\cup\{f_1,\ldots,f_{r}\}$ is dependent, but if we remove $f_r$ it becomes independent. So it contains a unique circuit (containing $f_r$), which may serve as $C_{k+1}$. Proceed this way.

Now the inequality ${\rm rank}(E)\geqslant {\rm rank}(M)+{\rm rank}(N)-1$ follows from the following two propositions:

1. $|E_1|-1={\rm rank}(C_1)\geqslant {\rm rank}_{M}(C_1)+{\rm rank}_N(C_1)-1$;

2. For each $k\geqslant 2$, $$|E_k\setminus E_{k-1}|-1\geqslant {\rm rank}_{M}(E_k)-{\rm rank}_{M}(E_{k-1})+{\rm rank}_{N}(E_k)-{\rm rank}_{N}(E_{k-1}).$$

We proceed with proving 1). Denote $C_1=\{1,2,\ldots,r\}$; ${\rm rank}_{M}(C_1)=\alpha$; let $x_1,\ldots,x_{\alpha}$ be an $M$-base of $C_1$. Assume that there exists $i\in \{1,2,\ldots,\alpha\}$ for which $y_i$ does not belong to a span of $y_{\alpha+1},\ldots,y_r$. Then there exists linear functionals $\eta,\nu$ on $X$, $Y$ respectively satisfying $\eta(x_i)=\nu(y_i)=1$, $\eta(x_j)=0$ for $j\in \{1,\ldots,\alpha\}\setminus \{i\}$, $\nu(y_j)=0$ for $j=\alpha+1,\ldots,r$. Then $\eta\otimes \mu$ applied to $x_j\otimes y_j$ equals 1 for $j=1$ and equals 0 for $j\in \{1,\ldots,\alpha\}\setminus \{i\}$. Thus $x_i\otimes y_i$ can not be a linear combination of other elements of our circuit, a contradiction. Therefore $y_{\alpha+1},\ldots,y_r$ span $y_1,\ldots,y_r$ and ${\rm rank}_N (C_1)\leqslant r-\alpha=|C_1|-{\rm rank}_{M}(C_1)$ that is 1).

The final step is 2). Denote $C_k\setminus E_{k-1}=\{1,\ldots,r\}. $Let $x_1,\ldots,x_{\alpha}$ form a basis of $C_{k}\setminus E_{k-1}$ in the matroid $M/E_{k-1}$ (that corresponds to factorizing modulo the span of $\{x_i:i\in E_{k-1}\}$.) So, $\alpha={\rm rank}_{M}(E_k)-{\rm rank}_{M}(E_{k-1})$. Again, assume that there exists $i\in \{1,2,\ldots,\alpha\}$ for which $y_i$ does not belong to a span of $y_{\alpha+1},\ldots,y_r$. Then there exists linear functionals $\eta,\nu$ on $X$, $Y$ respectively satisfying $\eta(x_i)=\nu(y_i)=1$, $\eta(x_j)=0$ for $j\in E_{k-1}\cup\{1,\ldots,\alpha\}\setminus \{i\}$ , $\nu(y_j)=0$ for $j=\alpha+1,\ldots,r$. We get a contradiction similarly to the proof of 1). Therefore ${\rm rank}_N(C_k\setminus E_{k-1})\leqslant r-\alpha$. But by Lemma 1 the matroid induced by $N$ on $C_{k}$ is connected, thus (the first inequality is a submodularity of the rank function) we get $${\rm rank}_N(E_k)-{\rm rank}_N(E_{k-1})\leqslant {\rm rank}_N(C_k)-{\rm rank}_N(C_k\cap E_{k-1})\\ \leqslant {\rm rank}_N(C_k\setminus E_{k-1})-1\\ \leqslant r-\alpha-1=|E_k\setminus E_{k-1}|-({\rm rank}_{M}(E_k)-{\rm rank}_{M}(E_{k-1}))-1$$ that proves 2).