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)

  • $\begingroup$ @D.W. I made an edit. You can't pick a random matrix. and it would be impossible to compute rank in a regular manner as the complexity would exceed the limit of $O(n^2)$ $\endgroup$ Jun 5 '17 at 18:33
  • $\begingroup$ I thought that the values will be a predefined gauss elimination values. BUT as I don't know the values of the matrix values before I'm prebuilding it (I.e which one is zero) I can't it doesn't looks like the it will fit. My direction is towards randomized algorithm ( fill the values with some randomize linear combination that might give a rank and can be easily computed). $\endgroup$ Jun 6 '17 at 6:27
  • $\begingroup$ As I mentioned to build an $n \times n$ matrix, you must compute the rank first on the large matrix and this is what I'm trying to prevent because of the high complexity of it. $\endgroup$ Jun 6 '17 at 6:30
  • $\begingroup$ OK. It might be helpful to edit the question to include that information. What is the best algorithm you know so far? How fast is it? What's the fastest algorithm you can find to compute the rank of $A$, given its special structure? $\endgroup$
    – D.W.
    Jun 6 '17 at 7:53