Let $m,n$ be two positive integers, with $m\geq n$. Suppose we have $m$ sets $A_1,\ldots, A_m\subseteq [n]$, with $|A_i|=d_i$. Let $\mathbb F$ be a finite field of size $q$.
Let $D$ be the set defined as
$$ D:=\left\{(i,j)\in [m]\times[n] \,|\, j \in A_i\right\}=\bigcup_{i=1}^m \{i\}\times A_i$$ We denote by $x=(x_{ij})_{(i,j)\notin D}$ and by $y=(y_{ij})_{(i,j)\in D}$.
Define the $m \times n$ matrix $B(x,y)$ as the matrix whose entries are given by
$$b_{ij}=\begin{cases} x_{ij} & \mbox{ if } (i,j)\notin D \\ y_{ij} & \mbox{ if } (i,j)\in D \end{cases} $$
I would like to find conditions on the following value
$$N:=\max_{\alpha=(\alpha_{ij})_{(i,j)\in D}} \min_{\beta=(\beta_{ij})_{(i,j)\in D}} \{rank(B(\alpha,\beta))|\alpha_{ij},\beta_{ij}\in \mathbb F\}.$$
Conjecture: $N$ is equal to the maximum integer $k$ such that there exist $P$ and $Q$ with $$PB(x,y)Q=\left[ \begin{array}{ccc|ccc} x_{i_1j_1} & & ? & \\ \vdots & \ddots & & &?\\ x_{i_kj_1} & \ldots & x_{i_kj_k} & \\ \hline \\ & ? & & & ? \\ \end{array}\right] $$
Partial proof: It is trivial to show that $N\leq k$. In fact by choosing $\alpha_{i_lj_l}=1$ for $l=1,\ldots,k$ and $\alpha_{i_lj_r}=0$ for $r<l$, we obtain a $k\times k$ submatrix whose determinant is $1$.
Some considerations: Actually I want to prove that, if there not exist such permutation matrices for some integer $k'$, then the ideal $$I_{k'}:=(\Delta_{I,J}(\alpha,y)|I\subseteq[m], J\subseteq [m], |I|=|J|=k')\subseteq\mathbb F[y],$$ is such that $$\mathcal V_{\mathbb F}(I_{k'})=\emptyset.$$ I am quite sure that for such ideal, (since it's generated by polynomials whose degrees in each variable is at most $1$) we have $$\mathcal V_{\mathbb F}(I_{k'})=\emptyset \Leftrightarrow \mathcal V_{\bar{\mathbb F}}(I_{k'})=\emptyset.$$
So, here my list of questions:
- Is this consideration about the algebraic sets true (in this case)?
- Is my conjecture true? If not, could someone help me to find a counterexample?
- Does my conjecture depend on the field size?
- If the conjecture is not true could it become true with some of the following simplifications
a) $d_i=d$ for every $i=1,\ldots, m$;
b) $m=n$;
c) $\alpha_{ij}\in\{0,1\}$ and $$\sum_{j=1}^n\alpha_{ij}=1$$ for every $i=1,\ldots,m$.
In particular I'm really interested in the simplifcatons $a)$ and $c)$.
Thank you in advance, Alessandro