Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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