# A Hadamard product of binary (or ternary) matroids

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$$.

• for $m=2$ it holds over any field: if $x_1,\ldots,x_{r_1}$ is a base of $M_1$, choose $i\in \{1,\ldots,r_1\}$ for which $y_i$ does not belong to a span of $\{y_{j}, j>r_1\}$ and linear functionals $\eta_1,\eta_2$ n corresponding spaces such that $\eta_1(x_i)=\eta_2(y_1)=1$, $\eta_2(y_j)=0$ for $j>r_1$, $\eta_1(x_j)=0$ for $j\in \{1,\ldots,r_1\}\setminus \{i\}$. Apply $\eta_1\otimes \eta_2$ to a linear combination of $x_i\otimes y_i$ which vanishes, we see that the coefficient of $x_i\otimes y_i$ is 0, thus it is not a circuit. Feb 22, 2021 at 12:13
• @FedorPetrov Thanks, I have actually proven the conjecture for any field in the cases I have stated (this is in the preprint).
– Ben
Feb 22, 2021 at 12:16

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\}). 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).

• Thank you -- This is a beautiful proof. I have sent an email to your gmail account.
– Ben
Mar 9, 2021 at 14:28