Suppose we have a field $K$ and a number of matrices $A_0,A_1,...,A_k \in K^{(n+1) \times n}$. I want to efficiently answer queries of the following form:
"For some $x \in K^{n+1}$ and $c_1,\dots,c_k \in K$ does there exist $y \in K^n$ such that $(A_0 + c_1 A_1 + \cdots + c_k A_k) y = x$ ?"
In other words, is $x$ in the image of $A_0 + c_1 A_1 + \cdots + c_k A_k$ ?
I know how to answer these queries (for example with the Rouché-Capelli theorem), but I am wondering if this can be done more efficiently? More precisely, I am wondering if it is possible to do some kind of precomputation on the $A_i$ such that answering the queries can be done faster?
I am mostly interested in the case that $k$ is small (something like $k=1$ or $k=2$), so an approach that only works for small $k$ is still very much appreciated.