Matrix $A$ such that for all matrices $B$ the product $AB$ has a row with not a single zero

Let $A$ be a given fixed $n \times m$ matrix. We also consider matrices $B$ of dimension $m \times p$. I am interested in those matrices $A$, for which for all $B \in \mathbb R^{m \times p}$ with non-zero columns, the product $AB$ has at least one row $r_i$, such that there is not a single 0 in the row $r_i$.

Is there already terminology for this? I would like to have a useful characterization of $A$ based on linear algebra. Thank you.

• Your class is empty, as $B:=0$ shows. So you want to prevent such things to happen :) – Loïc Teyssier Jul 11 '14 at 8:17
• Still, such matrices do not exist, just take the first column of $B$ to be a solution of $a_{11}x_1+\cdots+a_{1m}x_m=0$. – Fernando Muro Jul 11 '14 at 8:26
• and then the first row is zero. but I didnt require all rows of $AB$ to be zero-free. There only has to be at least one. Correct me if i got you wrong. – user45183 Jul 11 '14 at 8:29
• You'll need $p<n$, or $m=1$. Otherwise, for each row of $A$, you can find an orthogonal vector (as long as $m>1$) and make that a column of $B$. If row$(A)_i\cdot$col$(B)_i=0$, then $(AB)_{i,i}=0$ for each $i$, so there's a zero in every row when there are as many columns as rows in $AB$. – Zack Wolske Jul 11 '14 at 8:53
• Seems like the condition you want is rank$(A) > p$. – Zack Wolske Jul 11 '14 at 8:58

If $\text{Ker}(A) \ne \{0\}$, $A$ certainly doesn't have the property, as you can take $B$ whose columns are all copies of a nonzero member of $\text{Ker}(A)$ and have $AB$ all $0$. So assume $\text{Ker}(A) = \{0\}$.

Now the columns of $AB$ are $p$ arbitrary members of $\text{Ran}(A)$ other than $0$. The question is whether there are $p$ members of $\text{Ran}(A)$ which together have at least one $0$ in every position. Let $V = \text{Ran}(A)$, which is a linear subspace of ${\mathbb R}^n$ of dimension $r = \text{rank}(A)$. Let ${\cal F}$ be the collection of sets $S \subseteq \{1,\ldots,n\}$ such that $\dim \{v \in V: v_i = 0 \; \forall i \in S\} > 0$. The condition then is that there do not exist $p$ members of $\cal F$ whose union is $\{1,\ldots,n\}$.

Note that $S \in {\cal F}$ is equivalent to $\text{Ker}(A_S) \ne \{0\}$, where $A_S$ is the $|S| \times m$ submatrix of $A$ consisting of the rows in $S$. In particular, $S$ contains all sets of cardinality $<r$. So certainly $p(r-1) < n$ is a necessary condition. But there may also be sets of greater cardinality, so this is not sufficient.

For a given $A$, even if you list all maximal members of $\cal F$ (and there might be a lot of them) you have a "set-covering problem" to determine if there are $p$ such sets that cover $\{1,\ldots, n\}$, so this might be a nontrivial computational problem. I suspect it is NP-complete.

You can assume that the top $m$ rows of $A$ form an identity matrix. That might help think about this.

If $A$ has the property then so does $AM$ for any invertible $m \times m$ matrix $M$ as $AB$ is bad exactly when $AM(M^{-1}B)$ is. So one can do column operations to put the matrix in column echelon form. One can also permute the rows of $A$ as that will only permute the rows of $AB$. If the rank of $A$ is less than $m$ one can reduce to a matrix with $j \ge 1$ all $0$ columns on the right. This simply makes the last $j$ rows of any $B$ irrelevant so those columns may be dropped without changing anything.

Roberts excellent solution then becomes: Consider all sets $S$ of rows which together have rank $m-1$. $A$ fails to have the desired property exactly when there are $p$ of them which together cover all the rows.

In the event that every $m$ rows of $A$ are independent we see that a column $Ax$ can have at most $m-1$ zeros. So in that special situation $p(m-1) \lt n$ is necessary and sufficient.

This is a simple observation and it is similar to Robert's answer, but perhaps it is worth making explicit anyway: Let $\mathcal A$ be the set of rows of $A$. Then your condition will hold precisely if it is not possible to partition $\mathcal A=\mathcal A_1 \cup \ldots \cup\mathcal A_p$ into (at most $p$) subsets with $\dim L(\mathcal A_j)<m$ for $j=1,\ldots ,p$.

Indeed, if we had such a partition, we could take $b_j\perp L(\mathcal A_j)$ as the columns of $B$, and the converse is also obvious, by defining $\mathcal A_j =\{b_j\}^{\perp}\cap \mathcal A$ .