Linear independence (${\sum }_i{a}_i{v}_i=0⟺a_1=\cdots =a_n=0$)

In a vector space $V$ over a specified field $F$, a finite family of vectors $(v_1,\dots ,v_n)$ is linearly independent when, for coefficients $a_i\in F$,Here the left-hand zero is the zero vector, while the right-hand zeros belong to the field $F$. Thus linear independence excludes every nontrivial linear relation. For an infinite family, require this condition for every finite subfamily.^[ref]

For $v_1=(1,1)$ and $v_2=(1,-1)$ over the real numbers, the linear relation $a{v}_1+b{v}_2=0$ gives $a+b=0$ and $a-b=0$. Adding and subtracting yields $2a=2b=0$, hence $a=b=0$. This verifies linear independence directly and explains why the linear combination giving $(3,1)$ has exactly the coefficients $(2,1)$.

A linearly independent family cannot contain the zero vector: a coefficient of $1$ on that entry and $0$ on every other entry would be a nontrivial linear relation. The empty family is linearly independent, because its empty sum is the zero vector and there are no coefficients that could be nonzero. Linear independence identifies a collection without redundant vectors; combined with a spanning set, it gives a basis. The uniqueness of linear combination coefficients makes its representations unambiguous.

In the one-sorted vector-space language naming each scalar multiplication, a first-order formula reduces by quantifier elimination to finitely many linear equations. An independent pair satisfies only the identically zero equations among them. A dependent pair $(x,ax)$ with nonzero $x$ satisfies the same listed equations if the scalar $a$ avoids their finitely many forbidden ratios, which is possible over an infinite field. Thus no formula defines pair independence. The complete independent-pair type is still consistent in an infinite-dimensional model; it is nonisolated.

Take independent uniform samples from a $d$-dimensional vector space over the two-element field. At current matrix rank $r$, the existing span contains $2^r$ of the $2^d$ possible vectors, so a new sample increases the matrix rank with probability $1-2^{r-d}$. The mean waiting time for that increase is $1/(1-2^{r-d})$ by the geometric distribution. Adding the waiting times gives $\mathbb{E}M=d+{\sum }_{j=1}^d(2^j-1{)}^{-1}<d+2$. For $d\ge 1$, the bound follows by separating $j=1$ and using $(2^j-1{)}^{-1}<2^{1-j}$ for $j\ge 2$; for $d=0$, no samples are needed.

After $m=d+t$ samples, failure to span implies that some nonzero linear functional vanishes on all samples. Each fixed nonzero functional does so with probability $2^{-m}$; the union bound over the $2^d-1$ possibilities gives failure less than $2^{-t}$. This provides both an expected sample count and a fixed-budget high-success version of Simon's algorithm.

A family is linearly independent if and only if every vector in its linear span has unique coefficients as a linear combination of that family. For a short proof, subtract two representations to get ${\sum }_i(a_i-b_i)v_i=0$; linear independence forces each difference to vanish. Conversely, uniqueness applied to the zero vector forces every linear relation to use only zero coefficients. This explains the practical role of linear independence: a coordinate vector relative to an ordered basis is unambiguous.

A finite vector family is minimally dependent if it is linearly dependent and every proper subfamily is linearly independent. For $n\ge 2$, the family $e_1,\dots ,e_{n-1},{\sum }_{j=1}^{n-1}{e}_j$ in ${\mathbb{R}}^n$ is an example. The sum supplies a nonzero dependence. If the sum vector is omitted, the remaining vectors are a coordinate basis; if $e_j$ is omitted, its coordinate in any proposed relation forces the coefficient of the sum vector to vanish, then all other coefficients vanish. Every smaller proper subfamily lies in one of these independent $(n-1)$-element subfamilies.

Let the first $k$ columns of a matrix be the first dependent prefix, with no zero column. Their relation space has dimension one, and every nonzero relation $b$ has at least two nonzero coordinates. If both $Ab=0$ and $A\mathrm{diag}({\lambda }_j)b=0$, one-dimensionality gives ${\lambda }_j{b}_j=c{b}_j$ for all $j$. Two nonzero coordinates would force two of the distinct weights ${\lambda }_j$ to agree, a contradiction.

A finite family of vectors in a vector space over a specified field $F$ is linearly dependent if it has a nontrivial linear relation: ${\sum }_i{a}_i{v}_i=0$ with $a_i\in F$ and at least one coefficient nonzero. One can then solve for a vector whose coefficient is nonzero as a linear combination of the others; removing that entry preserves the linear span. Repeated vectors in a list give linear dependence: for example $(v,v)$ has the linear relation $1v+(-1)v=0$. A list keeps both entries even though the set $\{v,v\}$ has only one element. Strang's notes illustrate redundant columns by expressing one as the sum of two others.^[ref]

Keep $v_1=(1,1)$ and $v_2=(1,-1)$, and add $v_3=(2,0)=v_1+v_2$. The three vectors still have linear span ${\mathbb{R}}^2$, but nowThe two coefficient triples $(2,1,0)$ and $(1,0,1)$ differ by the nontrivial linear relation $(-1,-1,1)$. In fact all linear combination representations of this target areTo check both completeness and correctness, use $c_1{v}_1+c_2{v}_2+c_3{v}_3=(c_1+c_3)v_1+(c_2+c_3)v_2$. Linear independence of $v_1,v_2$ forces $c_1+c_3=2$ and $c_2+c_3=1$, giving exactly the displayed family. Redundancy therefore preserves attainable targets while allowing their coefficients to move. For solving a linear system, these alternatives matter; for assigning unique coordinate vectors, one instead chooses a basis.

The following example shows why linear independence depends on the scalar field.

Consider the vectors $1,i$ in the complex numbers, where $i$ is the imaginary unit. With scalar field $\mathbb{R}$, a linear relation $a\cdot 1+b\cdot i=0$ has $a,b\in \mathbb{R}$. Taking its real part and imaginary part gives $a=b=0$, so the pair is linearly independent. Every complex number $x+iy$ also has coefficients $(x,y)$ in the real numbers, so $1,i$ form a basis and the dimension of a vector space is two.

With scalar field $\mathbb{C}$, the same pair is linearly dependent, sinceuses the nonzero coefficients $(i,-1)$ from the complex numbers. The single vector $1$ is now a basis, because $z=z\cdot 1$ for every complex number $z$, giving dimension of a vector space one. For example $3+i=3\cdot 1+1\cdot i=(3+i)\cdot 1+0\cdot i$: the second representation uses a coefficient unavailable over the real numbers. Specifying the field is part of the definition of linear independence.

A linear relation among vectors $v_1,\dots ,v_n$ is a coefficient tuple $(a_1,\dots ,a_n)$ satisfying ${\sum }_i{a}_i{v}_i=0$. It is nontrivial if at least one coefficient is nonzero. For the matrix with these vectors as columns, the space of relations is its kernel. The vectors are linearly independent exactly when this kernel is zero. An invertible change of coordinates preserves every relation, since $S{\sum }_i{a}_i{v}_i=0$ if and only if ${\sum }_i{a}_i{v}_i=0$.