Check whether a given set of vectors is linearly independent. Vectors are linearly independent if no vector in the set can be expressed as a linear combination of the others, which is equivalent to the matrix formed by these vectors having full column rank.
from typing import List
def check_linear_independence(vectors: List[List[float]], tol: float = 1e-9) -> bool:
if not vectors:
return True
n_vectors = len(vectors)
dim = len(vectors[0])
# Build matrix with vectors as columns
# Then check if rank equals number of vectors
m = dim
n = n_vectors
mat = [[vectors[j][i] for j in range(n)] for i in range(m)]
rank = 0
for col in range(n):
pivot = -1
max_val = tol
for row in range(rank, m):
if abs(mat[row][col]) > max_val:
max_val = abs(mat[row][col])
pivot = row
if pivot == -1:
continue
mat[rank], mat[pivot] = mat[pivot], mat[rank]
for row in range(rank + 1, m):
if abs(mat[row][col]) > tol:
factor = mat[row][col] / mat[rank][col]
for j in range(col, n):
mat[row][j] -= factor * mat[rank][j]
rank += 1
return rank == n_vectors