I have an homework where I need to investigate how the rank of a matrix relates to the connectivity of the associated graph. I have run some simulations and the claim below seems to hold, but I have no clue how to show it. Could you help?
MATRIX
Consider a matrix $A$ structured as follows $$ A=\begin{pmatrix} A_1\\ A_2\\ \vdots\\ A_N \end{pmatrix} $$ where, for each $n\in \{1,...,N\}$, $A_n$ is a $T_n\times (NK+KJ)$ matrix.
Consider some numbers $\{k_{nt}\}_{n=1,...,N, t=1,...,T_n}$ where each $k_{nt}\in \{1,...,K\}$.
Consider some numbers $\{j_{nt}\}_{n=1,...,N, t=1,...,T_n}$ where each $j_{nt}\in \{1,...,J\}$.
For each $n\in \{1,...,N\}$, every $t$-th row of the matrix $A_n$ is structured as follows:
The $\Big((n-1)K+k_{nt}\Big)$-th element is equal to $1$.
The $\Big(KN+(j_{nt}-1)K+k_{nt}\Big)$-th element is equal to some scalar $\delta_{nt}>0$.
All the other elements equal to zero.
Further, the matrix $A$ contains no zero columns and $\sum_{t=1}^{N} T_n \geq (NK+KJ)$.
GRAPH
Draw a a bipartite graph as follows:
In one side (hereafter, side 1), we list all the pairs $\{j,k\}$ from $\{1,...,J\}\times \{1,...,K\}$.
In the other side (hereafter, side 2), we list all the indices $n$ from $\{1,...,N\}$.
We draw an edge from pair $\{j,k\}$ to index $n$ if there is $t\in \{1,...,T_n\}$ such that $j_{nt}=j$ and $k_{nt}=k$.
Question: I want to show that a necessary condition for the matrix $A$ to have full column rank is that in the graph:
every pair $\{j,k\}$ in side 1 should be (indirectly) connected to at least another pair $\{j',k'\}$ in side 1.
every index $n$ in side 2 should be (indirectly) connected to at least another index $n'$ in side 2.