Let $A$ be a matrix where $A \in \mathbb{F}^{n^s \times n^s}$ and $s>2$. Assume $A$ is a sparse matrix where its rank $\leq n$ and that there is only constant number of non-zero elements in each row. The positions of the non-zero elements are predefined.
My question: How can I fill a matrix of size $n \times n$ with an equal rank that each value is computed from the original matrix, where the complexity of that building would be $O(n^2)$? (randomized algorithms can also be considered)
