Not necessarily.

If this would hold, all components of the $y_i$ would be bounded in terms of $A$; so, by compactness argument, the same would hold for matrices and columns with *non-negative* entries. We will show that this is not the case.

Let $I$ and $J$ be the identty and the all-ones matrices of order $3\times3$. Set
$$
A=\left[\matrix{ 100I&J\\J&100I}\right].
$$
Then each $y_i$ may contain at most one non-zero among the first three entries, the same for the last three. On the other hand, for each $a=1,2,3$ and $b=4,5,6$ there should be a $y_i$ with non-zero $a$th and $b$th entries. Thus $k\geq9$.

**Remark.** This argument shows that, in general, $k\geq [n^2/4]$. It cannot show more, since the edges of an arbitrary graph on $n$ vertices may be split into at most $n^2/4$ cliques. It may happen that this estimate is sharp.