Graph Algorithm Library

2 Preliminaries

2.1 Tensor Product

Lemma 2.1.1 The tensor product of linearly independent families

Let \(R\) be a domain and \(M, N\) two \(R\)-semimodules. If \(f\) and \(g\) are linearly independent families of points in \(M\) and \(N\), then \((i, j) \mapsto f i \otimes g j\) is a linearly independent family of points in \(M \otimes N\).

Proof

We will prove the equivalent statement:

Let \(P, Q\) be two free \(R\) modules, \(f : P \to M\) and \(g : Q \to N\) be two \(R\)-linear injective maps. Then \(f \otimes g : P \otimes _R Q \to M \otimes _R N\) is injective.

Let \(K\) be the field of fractions of \(R\).

The map

\[ P \otimes _R Q \to (K \otimes _R P) \otimes _R (K \otimes _R Q) = (K \otimes _R P) \otimes _K (K \otimes _R Q) \]

is injective because \(R \to K\) is injective and all the modules involved are flat. The map

\[ (K \otimes _R P) \otimes _K (K \otimes _R Q) \to (K \otimes _R M) \otimes _K (K \otimes _R N) \]

is injective because all the modules involved are \(K\)-flat (as \(K\) is a field).

\(P \otimes _R Q \to M \otimes _R N\) is now a factor of the composition of the two injections above, and is thus is injective.