In the question below I have to prove that the span of a set of length $k$ is in the space $R^n$. The question is stated as:
Let $(p^1, . . . , p^k) ⊂ R^n$, where $k ≥ n$.
Does $span[(p^1, . . . , p^k)] = R^n$? (i.e. does the set $(p^1, . . . , p^k)$ contains $n$ linearly independent vectors?)
I need to show how I can solve this decision problem by solving at most $n$ linear programming problems.
I can also make use of the following result for this:
Let ${q^1 , . . . , q^n} ⊂ R^n$ be a basis for $R^n$. Then $span[(p^1
> , . . . , p^k)]=R^n$ if and only if $q^j∈span[(p^1 , . . . , pk)]$ for
each $j = 1, . . . ,n.$
My thinking for this question is to show that the set $(p^1, . . . , p^k)$ has full row rank (where the number of rows is $n$), which in turn means that the span of $(p^1, . . . , p^k)$ is equal to $R^n$ and the set contains $n$ linearly independent vectors.
Is there any way to prove this?
Best Answer
You want to check for $i=1,\ldots, n$, whether $$e_i=\sum p^ix_i$$ has a solution. This is a feasibility problem.
If the answers to all of them is yes, then it contains $n$ linearly independent vector.