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$)

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.

• 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? – user58955 Oct 1 '13 at 1:17