Full rank of Hadamard product matrix

Question

Let $\circ$ be the Hadamard product and consider two matrices $C \in\{0,1\}^{N \times n}$ and $W\in \mathbb{R}^{N\times n}$: $$ C:=\left[\begin{array}{cccc} c_1^1 & c_2^1 & \cdots & c_n^1 \\ \vdots & c_2^2 & \cdots & \vdots \\ \vdots & \cdots & \ddots & \vdots \\ c_1^N & \cdots & \cdots & c_n^N \end{array}\right],W:=\left[\begin{array}{cccc} w_1^1 & w_2^1 & \cdots & w_n^1 \\ \vdots & w_2^2 & \cdots & \vdots \\ \vdots & \cdots & \ddots & \vdots \\ w_1^N & \cdots & \cdots & w_n^N \end{array}\right]. $$ Therefore, we have: $$ C\circ W:=\left[\begin{array}{cccc} c_1^1 w_1^1 & c_2^1 w_2^1 & \cdots & c_n^1 w_n^1 \\ \vdots & c_2^2 w_2^2 & \cdots & \vdots \\ \vdots & \cdots & \ddots & \vdots \\ c_1^N w_1^N & \cdots & \cdots & c_n^N w_n^N \end{array}\right]. $$ We know that $N<n$, $W$ has full rank $N$ and the entries of $C$ can assume values only $0$ or $1$.

Moreover, $C$ has at least one element that is $1$ in every row and every row is different from the other ones. Finally, $c_j^i=1\Leftrightarrow w^j_i>0$. Therefore, $C\circ W$ has only non-negative entries.

These assumptions are enough for saying that $C\circ W$ has full rank $N$? If not, what are the right assumptions that one should add for obtaining that rank of $C\circ W$ is $N$?

Answer 1

Here is an example which shows that full-rank $C$ is not always sufficient to ensure that $W\cdot C$ has full rank. Both $W$ and $C$ have full rank, but $W\cdot C$ does not.

$$W = \begin{pmatrix} 1 & 2 & 3 & 3 \\ 1 & 1 & -4 & 1\\ -3 & 1 & 3 & 2\end{pmatrix} $$ $$C = \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} $$ $$W\cdot C = \begin{pmatrix} 1 & 2 & 3 & 3 \\ 1 & 1 & 0 & 1\\ 0 & 1 & 3 & 2\end{pmatrix} $$

In $W\cdot C$, the first row is the sum of the other two rows.

I'm confident that any number of rows and columns can give a similar counterexample with at most one 0 per row of $C$.

NEW: There are some values of $C$ such that $W\cdot C$ has full rank whenever $W$ satisfies the conditions. The simplest example is the identity matrix. More generally, if $C$ has a unique transversal (set of 1s, one per row, in different columns) then $W\cdot C$ has full rank whenever $W$ satisfies the conditions. It is plausible that those are the only examples, but I'm not sure about it.

NEWER: I didn't write a detailed proof, but I believe that if $C$ doesn't have full rank there is always a counterexample (i.e., one can find $W$ of full rank such that $W\cdot C$ is not of full rank). Reorder the rows of $C$ so that a row full of 1s, if any, is first, and there is a linear relation $R$ that defines the last row in terms of earlier rows. Now we construct $W$ out of $C$. The first $N-1$ of rows of $W$ are those rows of $C$ with a tiny random negative perturbation of every entry. With probability 1, those $N-1$ rows of $W$ are linearly independent. The final row of $W$ is constructed from the final row of $C$ thus: Where $C$ has 0, enter a random negative number in $W$. Where $C$ has 1, apply relation $R$ to determine the entry in $W$ (since the first $N-1$ rows were only perturbed by tiny amounts, this will give a positive value). Now I believe that with probability 1, $W$ has full rank. However, $W\cdot C$ satisfies the relation $R$.

SO FAR (always assuming the given conditions on positivity and structure):

(1) If $C$ has less than full rank, then there is some $W$ of full rank such that $W\cdot C$ does not have full rank. (But some other $W$ of full rank might give $W\cdot C$ full rank.)

(2) If $C$ has a unique transversal (which is an example of full rank), then for every $W$ of full rank, $W\cdot C$ also has full rank. This can be generalised to the case that some $n$ columns of $C$ have a unique transversal.

(3) If $C$ has full rank but is not in case (2), I don't know the answer.

The example at the start of this answer is in case (3), so it is not true that full rank $C$ is always enough to give full rank $W\cdot C$.

EVEN NEWER: Here is a theorem. It applies only to the square ($N=n$) case at the moment and extending it to the rectangular case will need some thought.

Consider two properties of $C$:

(A) For every $W$ which has a positive value wherever $C$ has 1, $W\cdot C$ is nonsingular.

(B) $C$ is nonsingular and has permanent equal to the absolute value of its determinant.

Theorem. (A) and (B) are equivalent.

Proof. [(B)$\implies$(A)]. Transversals correspond to permutations and have parity even/odd. Condition (B) says that $C$ has at least one transversal and all transversals have the same parity. This means that all the non-zero terms in the expansion of the determinant of $W\cdot C$ have the same sign, so their sum is not zero.

[(A)$\implies$(B)]. Suppose $C$ has an even transversal $M_e$ and an odd transversal $M_o$. Form a matrix $W_e$ like this: put a very large positive value where $M_e$ is, a tiny positive value in the other places where $C$ has 1, and a random negative value where $C$ has 0. Form $W_o$ in the same way using $M_o$. Now, $W_e\cdot C$ has positive determinant, and $W_o\cdot C$ has negative determinant. Since the determinant of a matrix is a continuous function of the matrix entries, there is $W$ which is a convex combination of $W_o$ and $W_e$ such that $W\cdot C$ is singular.

In the non-square case ($N<n$), we can generalize (B):

(B') Some $N\times N$ submatrix of $C$ is nonsingular and has permanent equal to the absolute value of its determinant.

Then the implication (B')$\implies$(A) holds, since $W\cdot C$ is full rank iff it has an $N\times N$ non-singular submatrix. The remaining question is whether (A)$\implies$(B') holds too.