2
$\begingroup$

We have $n$ vectors each with $k$ components. Let $V$ be their span and $r$ be the dimension of $V$. Then $r \leq k$.

I encountered this in a paper I am reading. I am not able to see why this is true(probably due to my not so sound linear algebra background).

Can anyone help me in understanding why the argument is true? Thanks.

Link to paper: https://www.cs.tau.ac.il/~shpilka/publications/RazShpilka_PIT.pdf

$\endgroup$
1
  • $\begingroup$ A spanning set can be reduced to a basis, so the dimension is less than or equal to the number of vectors you started out with. $\endgroup$
    – twosigma
    May 20, 2020 at 9:17

2 Answers 2

Reset to default
3
$\begingroup$

Let $\Bbb F$ be the underlying field. A vector with $k$ components is a vector in $\Bbb F^k$, which is a vector space of dimension $k$. If $V$ is the span of $n$ vectors in $\Bbb F^k$, then it is a subspace of $\Bbb F^k$: in particular, its dimension is less or equal to the dimension of $\Bbb F^k$, that is, $k$.

$\endgroup$
1
  • $\begingroup$ Got it. Thank you! $\endgroup$
    – Sumukha Bharadwaj
    May 20, 2020 at 11:07
1
$\begingroup$

Denote the $n$ vectors by $v_1, \cdots, v_n \in W$ (where $W$ is the vector space you're working with). To say that each vector has $k$ components is the same as saying that $W$ is $k$-dimensional, that is, that there exist $k$ linearly independent vectors $e_1, \cdots, e_k$ such that their span is equal to $W$ and that no combination of less than $k$ vectors can possibly span $W$ (and of course, also that any combination of more than $k$ vectors is linearly dependent). So the result you want follows by the very definition of dimension and basis.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .