1
$\begingroup$

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)

$\endgroup$

closed as unclear what you're asking by D.W., Robin Kothari, Kaveh, David Eppstein, Lev Reyzin Jun 15 '17 at 16:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – user1387682 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$ – user1387682 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$ – user1387682 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