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