7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 22 at 12:13
  • $\begingroup$ @FedorPetrov Thanks, I have actually proven the conjecture for any field in the cases I have stated (this is in the preprint). $\endgroup$
    – Ben
    Feb 22 at 12:16
1
+50
$\begingroup$

I hope that below is the proof of Conjecture, 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_m)+{\rm rank}(E\setminus E_m)={\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).

$\endgroup$
1
  • $\begingroup$ Thank you -- This is a beautiful proof. I have sent an email to your gmail account. $\endgroup$
    – Ben
    Mar 9 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.