Linear combination

Università di L’Aquila Claudio Arbib

Operations Research

Bases of IRⁿ

Content

• Linear, affine, conic and convex combination

• Linear and affine dependence and independence

• Rank and determinant

• Base for a set of vectors in IRⁿ

• Representation theorem

• Substitution theorem (Steinitz)

• Linear matroid

Linear combination

1 2

0 3

1

= λ₁ + λ₂ 4

with λ₁ = –2/3, λ₂ = 1

–2/3(0 , 3) +1(1 , 4)

Definition A vector x ∈ IRⁿ is said to be a linear combination of vectors a₁, …, a_m ∈ IRⁿ with

coefficients λ₁, ..., λ_m ∈ IR if x = λ₁a₁ + … + λ_ma_m

Example

Affine combination

Example

1 2

0 2

½

= λ₁ + λ₂ 2

with λ₁ = –1, λ₂ = 2

–1(0 , 2)

+2(½ , 2)

Definition A vector x ∈ IRⁿ is said to be an affine combination of vectors a₁, …, a_m ∈ IRⁿ with coefficients λ₁, ..., λ_m ∈ IR if

x = λ₁a₁ + … + λ_ma_m and

λ₁ + ... + λ_m = 1

Conic combination

Example

1 3

0 2

2

= λ₁ + λ₂ 2

with λ₁ = 1, λ₂ = ½

+1(0 , 2)

+½(2 , 2)

Definition A vector x ∈ IRⁿ is said to be a conic combination of vectors a₁, …, a_m ∈ IRⁿ with

coefficients λ₁, ..., λ_m ∈ IR if x = λ₁a₁ + … + λ_ma_m and

λ₁, ..., λ_m > 0

Convex combination

Definition A vector x ∈ IRⁿ is said to be a convex combination of vectors a₁, …, a_m ∈ IRⁿ with coefficients λ₁, ..., λ_m ∈ IR if

x = λ₁a₁ + … + λ_ma_m and

λ₁ + ... + λ_m = 1 λ₁, ..., λ_m > 0

+½(0 , 2)

+½(2 , 2) 1

2

0 2

2

= λ₁ + λ₂ 2

with λ₁ = ½, λ₂ = ½ Example

Hulls

Definition The affine (conic, convex) hull of a set S ⊆ IRⁿ is the set of all the vectors x ∈ IRⁿ which can be obtained as affine (conic, convex) combination of vectors of S.

Example

cone(S)

aff(S) conv(S)

Dependence and independence

Definition A set A = {a₁, …, a_m} ⊆ IRⁿ is linearly dependent if there exist m not identically null real numbers λ₁, …, λ_m such that

λ₁a₁ + … + λ_ma_m = 0.

Example

A = { ¹₂ , } is linearly independent²₁

B = { , , } is linearly dependent

(λ₁ = λ₂ = 2/3, λ₃ = –1)

1 2

2 1

2 2

Affine dependence is defined in a similar way adding the clause λ₁ + … + λ_m = 0.

Dependence and independence

Definition A set A = {a₁, …, a_m} ⊆ IRⁿ is affinely dependent if there exist m not identically null real numbers λ₁, …, λ_m such that

λ₁ + … + λ_m = 0 and λ₁a₁ + … + λ_ma_m = 0.

Example

B = { ¹ , , } is affinely independent

2

2 1

2 2

C = { , , } is affinely dependent

(λ₁ = λ₃ = –1, λ₂ = 2)

1 2

2 1

3 0

Dependence and independence

Proposition The following statements are equivalent:

1) a₁, a₂, …, a_m are affinely (in)dependent

2) a₁ – a_m, a₂ – a_m, …, a_m–1 – a_m are linearly (in)dependent

B = { ¹₂ , ²₁ , } is affinely independent²₂ D = { ^–1₀ , _–1⁰ } is linearly independent

Dependence and independence

Proposition The following statements are equivalent:

1) a₁, a₂, …, a_m are affinely (in)dependent

2) a₁ – a_m, a₂ – a_m, …, a_m–1 – a_m are linearly (in)dependent

E = { , } is linearly dependent

(λ₁ = –1, λ₂ = 2)

–2 2

–1 1

C = { , , } is affinely dependent

(λ₁ = λ₃ = –1, λ₂ = 2)

1 2

2 1

3 0

Dependence and independence

Proof (1) is true, there exist not identically null λ₁, …, λ_m ∈ IR such that λ₁a₁ + … + λ_ma_m = 0 (i) λ₁ + … + λ_m = 0 (ii) Then

λ₁(a₁ – a_m) + … + λ_m–1(a_m–1 – a_m) =

= λ₁a₁ + … + λ_m–1a_m–1 – (λ₁ + … + λ_m–1)a_m =

= – λ_ma_m – (λ₁ + … + λ_m–1)a_m =

= – (λ₁ + … + λ_m)a_m = 0

Note that it cannot be λ₁ = … = λ_m–1 = 0 otherwise (ii) would imply λ_m = 0.

This proves (2).

Proposition The following statements are equivalent:

1) a₁, a₂, …, a_m are affinely (in)dependent

2) a₁ – a_m, a₂ – a_m, …, a_m–1 – a_m are linearly (in)dependent

Dependence and independence

Proof Conversely, (2) implies the existence of µ₁, …, µ_m–1 ∈ IR not identically null and such that µ₁(a₁ – a_m) + … + µ_m–1(a_m–1 – a_m) = 0

namely

µ₁a₁ + … + µ_m–1a_m–1 – (µ₁ + … + µ_m–1)a_m = 0

Set λ_i = µ_i for i = 1, …, m – 1, λ_m = – (µ₁ + … + µ_m–1): then λ₁ + … + λ_m = 0, and there exists at least one λ_k ≠ 0. This proves (1).

Proposition The following statements are equivalent:

1) a₁, a₂, …, a_m are affinely (in)dependent

2) a₁ – a_m, a₂ – a_m, …, a_m–1 – a_m are linearly (in)dependent

Esercise Show that (1) and (2) are equivalent to

3) ^a1 , …, ∈ IRⁿ⁺¹ are linearly (in)dependenti

–1

a_m

–1

Rank

Definition Let A = {a₁, …, a_m} ⊆ IRⁿ. The largest number rg(A) of vectors in A which are linearly independent is called the rank of A.

Examples

B = { ¹ , , } has rank 2

2

2 4

2

A = { ¹ , , } has rank 2 5 2

2 1

3 0

C = { ¹ , , } has rank 1

–2

–4 8

–3

6 D = { ¹ , } has rank 2

2

2 1

E = { ¹ , } has rank 1

2

2

4 F = { ¹ } has rank 1

2

Rank

A matrix A ∈ IR^n×m defines two sets of vectors:

• C, formed by its n columns,

• R, formed by its m rows.

The largest number of linearly

independent vectors in C coincides with the largest number of linearly

independent vectors of R, and is called the rank of matrix A: rg(A).

One clearly has

• rg(A) = rg(A^T)

• rg(A) < min{m, n}

1 –3 2 0

–2 6 –4 0

A =

rg(A) = 1 Example

1 –3 2 0

–1 –7 4 –2

1 2 –1 1

A =

rg(A) = 2

Rank

Proposition The following statements are equivalent:

1) the system of linear equations Ax = b has a solution 2) rg(A) = rg(A, b)

Proof Let b = 0. In this case both statements are trivially true. In fact, the system Ax = b has x = 0 as a trivial solution; and adding b = 0 to any subset S of columns of A makes S linearly dependent: hence adding b to A cannot increase the rank of A, and therefore rg(A) = rg(A, b).

Suppose now b ≠ 0. If Ax = b has a solution x^°, this is clearly ≠ 0: then, since b can be expressed as a linear combination of the columns of A with not identically null coefficients x₁^°, …, x_n^°, [A, b] is a dependent set of vectors. Hence rg(A) = rg(A, b).

Conversely, let S be a set of linearly independent columns with |S| = rg(A).

If rg(A) = rg(A, b), then S is also an independent in [A, b] of maximum size, thus S ∪ {b} is linearly dependent, and therefore ∃x: Ax = b.

Determinant

Definition Let A ∈ IR^n×n. The determinant of A is the real number det(A) defined as follows:

1) if n = 1, then A = [a₁₁] and det(A) = a₁₁

2) if n > 1 then det(A) = Σ_j=1..n ^{(–1)i+j a}_ij^det(A_ij⁾

where A_ij is the submatrix (n – 1)×(n – 1) obtained by deleting the i-th row and the j-th column of A.

Example

1 2 1

A = 2 0 –3

0 –1 1

det(A) = (–1)²⁺¹2 det ^{2 1} +

–1 1

(–1)²⁺²0 det ^{1 1} +

0 1

(–1)²⁺³(–3) det ¹_{0 –1} ² =

= –2(2 + 1) + 0(1 – 0) + +3(–1 – 0) = –9

Notice: computing det(A) by starting from any other row or column yields the same result

Determinant

Definition A matrix B ∈ IR^n×n is said to be singular if det(B) = 0.

Proposition Let A ∈ IR^m×n with m < n. Then the homogeneous system of equations Ax = 0 has a non-trivial solution (that is, x ≠ 0) iff ∃B ⊆ A, B ∈

IR^m×m, such that det(B) = 0.

Corollary The columns (and the rows) of B are linearly dependent iff det(B) = 0.

Consequently:

For any A ∈ IR^m×n, rg(A) is the order of the largest square non- singular submatrix B of A.

Bases

Definition Let S ⊆ IRⁿ. A set B = {b₁, …, b_m} ⊆ IRⁿ is said to be a base for S if

• B is linearly independent

• B ∪ {x} is lin. dependent for any x ∈ S – B

(in other words, there exist not identically null real coefficients λ₀, λ₁, ..., λ_m such that λ₀x + λ₁b₁ + … + λ_mb_m = 0).

Observe that x 0 implies λ₀ 0, or B would not be independent.

Then we can write

x = – λ₁b₁/λ₀ – … – λ_mb_m/λ₀

(representation of x in B)

Bases

Theorem 1 The representation of x ∈ S in a given base B is unique.

Proof: assume

x = α₁b₁ + … + α_mb_m x = γ₁b₁ + … + γ_mb_m Then

0 = (α₁ – γ₁)b₁ + … + (α_m – γ_m)b_m

and if ∃i: α_i – γ_i 0, then B is linearly dependent (contradiction).

Bases

Theorem 2 Let x ∈ S – B, with B base for S e x 0. Suppose x = α₁b₁ + … + α_mb_m with α₁ 0.

Then B’ = {x, b₂, …, b_m} is a base for S.

Proof: first of all, B’ is independent. If not:

0 = µ₁x + µ₂b₂ + … + µ_mb_m

with µ₁ 0 (if µ₁ = 0, then B would be dependent).

Moreover, B’ is maximal in S, because y = λ₁b₁ + … + λ_mb_m ∀y∈S and

replacing b₁ = x/α₁ – α₂b₂/α₁ – … – α_mb_m/α₁ one obtains a representation of y in B’.

But then

x = – µ₂b₂/µ₁ – … – µ_mb_m/µ₁

x = α₁b₁ + α₂b₂ + … + α_mb_m contradiction

Linear matroid

Theorem 3 Let U be a finite set of vectors of IRⁿ, and ℑ the collection of all the subsets X of U which are linealry independent.

Then (U, ℑ) is a matroid.

Proof: first, ℑ is clearly subclusive, because every subset of an independent set is independent as well.

Let us show that the exchange property holds:

∀A, B ∈ ℑ: |B| > |A|, ∃x ∈ B – A: A ∪ {x} ∈ ℑ

that is, an element of the largest linear independent set can be added to the smallest, with the resulting set still being independent.

Linear matroid

Theorem 3 Let U be a finite set of vectors of IRⁿ, and ℑ the collection of all the subsets X of U which are linearly independent.

Then (U, ℑ) is a matroid.

Proof (continued): Let

A = {a₁, …, a_m} B = {b₀, b₁, …, b_m}

Should not the exchange property hold, then A∪{b_i} would be dependent ∀i: b_i ∉ A, that is, A is a base for B.

Assume b_m ∉ A: let then b_m = λ₁a₁ + … + λ_ma_m and without loss of generality suppose λ_m 0. Then by Theorem 2 one can replace b_m for a_m, and

A_m = {a₁, …, a_m–1, b_m} still is a base for B.

If instead b_m ∈ A, the substitution returns A_m = A which still is base for B by assumption.

Linear matroid

Theorem 3 Let U be a finite set of vectors of IRⁿ, and ℑ the collection of all the subsets X of U which are linearly independent.

Then (U, ℑ) is a matroid.

Proof (continued): Going ahead in this way, if b_m–1 ∉ A we can write b_m–1 = µ₁a₁ + … + µ_m–1a_m–1+ µ_mb_m

noticing that µ_m–1 0 (otherwise B would be dependent).

Then A_m–1 = {a₁, …, a_m–2, b_m–1, b_m}

A_m–2 = {a₁, …, a_m–3, b_m–2, b_m–1, b_m} …

… A₁ = {b₁, …, b_m–3, b_m–2, b_m–1, b_m} = B – {b₀}

are all basis for B. But then using A₁ we can represent b₀ in terms of b₁, …, b_m, contradicting the independence of B.