Suppose that $A$ is an $n \times n$ matrix, and I have observed some entries of $A$, say, $A_S$ ($A$ restricted on $S$) for some subset $S$ in $\{1,...,n\} \times \{1,...,n\}$. I want to know if it's possible that $A$ has rank $1$.

So this can be reformulated as the following question: does there exist vectors $x$ and $y$ such that $xy^T$ restricted on $S$ equal to the observed values $A_S$?

Is there a good way to test this in Mathematica? (the dimension $n$ could be large, but the set $S$ would be a set of a relatively small size in comparison with $n^2$)


1 Answer 1


This is the first approach that comes to my mind:

If Matrix $A$ has rank 1 every row-(or column)vector has to be a multiple of any other row(respectively column)-vector in the matrix $A$. Let's create an example:

ClearAll[a, A, vars, vars2, n, b]
n = 5;(*set dimension*)
A = Array[a, {n, n}];(*create matrix*)
vars = Flatten[A];(*create array of variables*)
(*set known entries entries*)
a[1, 2] = 3;
a[2, 3] = 1;
a[3, 3] = 2;
a[2, 4] = 5;
a[5, 3] = 2;
a[1, 5] = 2;
vars = Complement[vars, {a[1, 2], a[2, 3], a[3, 3], a[2, 4], a[5, 3], a[1, 5]}];(*remove the set elements from the variables list*)

To check that you could create a system of equations using Subsets to create pairs of row vectors and introduce new variables b[i], which represent the scalar multiples.

subsets = Subsets[A, {2}];(*every combination of row vectors of matrix A*)
vars2 = Array[b, Length[subsets]];(*add new variables for each set of row vectors*)
vars = Join[vars, vars2];

Then solve the system with respect to b[i] and all the other entries of $A$ not in $S$.

Solve[Table[subsets[[i, 1]] == vars2[[i]]*subsets[[i, 2]], {i,Length[subsets]}], vars]

If the solution set is empty your matrix has rank greater than one, if there exists a solution your matrix has rank 1.

  • $\begingroup$ I see, you're trying to solve for the ratios of any two rows. I think Solve[] could be slow when $n$ is large, any idea of how to make it scalable? $\endgroup$
    – user58955
    Commented Oct 1, 2013 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.