Linear transformation invariant wrt. maximum. All matrices are real. Define the operator $\max$ on matrices as a function that returns the largest value in each row.
Consider a matrix $F$ of size $n \times l$. The matrix has the property that any vector $v$ of the form $v(i) = F_{i,q(i)}$ for any mapping $q$ is in the range of some matrix $A$ of size $n \times k$.
Is it possible to find a matrix $C$ of size $k \times n$ such that we have:
$C \max F = \max C F$
If not, is it possible to at least find such a matrix $C$ with $O(k)$ rows?

Independent of the property of the matrix $F$, it is always possible to find such a matrix $C$. Pick any "rectangular permutation matrix" (Not sure if that is an well-established term)  $C$, which has in every row exactly one entry with $1$ and else zero entries and in every column at most one entry with $1$ and otherwise zero entries. 
Now, $CF$ basically contains in it rows a subset of the rows of $F$ and thus $\max CF$ is the same as picking the max values of the corresponding rows of $F$, thus $C \max F$, hence $C \max F = \max C F$. 
$C$ are not very fancy and I am not sure if that is what you were looking for, but that should answer the stated problem.
