Computation of Span and Basis of Vectors by Using C (Linear Algebra: Vector Spaces)

COMPUTATION OF SPAN AND BASIS OF VECTORS BY USING C

Computing the span and basis of a set of vectors using C involves implementing matrix operations, specifically row reduction to achieve row echelon form. This process identifies the linearly independent vectors that form the basis and by extension, define the span.

1. Representing vectors and matrices

Vectors can be represented as arrays, and a set of vectors can be combined into a matrix where each vector is a column (or row, depending on convention). A 2D array is suitable for matrix representation in C.

C

typedef struct {

int rows;

int cols;

double **data;

} Matrix;

// Function to create a matrix

Matrix* createMatrix (int rows, int cols) {

Matrix* mat = (Matrix*) malloc (sizeof (Matrix));

mat−>rows = rows;

mat−>cols = cols;

mat−>data = (double**)malloc (rows * sizeof (double) *));

for (int i=0; i < rows; i++) {

 mat−>data[i] = (double*)malloc (cols * sizeof (double));

}

return mat;

}

// Function to free matrix memory

void freeMatrix (Matrix* mat) {

for (int i=0; i < mat−> rows; i++) {

free (mat−>dat[i]);

}

free (mat−>data);

free (mat);

}

2. Implementing Row Reduction (Gaussian Elimination)

The core of finding the basis lies in transforming the matrix into row echelon form. This involves:

• Pivoting: Selecting a non−zero element (pivot) in a column and moving its row to the top (if necessary).

• Scaling: Dividing the pivot row by the pivot element to make the pivot 1.

• Elimination: Using the pivot row to make all other elements in the pivot column zero.

C

void rowReduce (Matrix*mat)

{

int lead = 0; // Current Leading column

for (int r = theta; r < mat−> rows & & lead < mat−> cols; r++) {

int i = r;

while (i < mat−> rows && fabs (mat−>data[i] [lead] < 1e−9)

{

// Find a non−zero i++;

}

if (i < mat−> rows) {

// Swap rows if necessary

if (i !=r) {

double* temp =  mat−>data[r]

mat−> dat[r] = mat−>data[i];

mat−>data[i] = temp;

}

// Scale pivot row

double div = mat−>data[r] [lead];

for (int j = lead; j < mat−>cols; j++) {

mat−>data[r][j] = div;

 }

// Eliminate other rows

For (int i_other = 0; i_other < mat−> rows; i−other++) {

if (i_other !=r) {

double mult = mat−>data[i_other] [lead];

for (int j = lead; j < mat−>cols; j++) {

mat−>data[i_other] [j] ‒= mult* mat−>data[r][j];

}

}

}

lead++;

}

}

}

3. Identifying the basis

After row reduction, the columns in the original matrix that correspond to the pivot columns (columns containing leading 1s in the row echelon form) form a basis for the span of the original vectors.

C

// Example usage:

// Assuming 'original_vectors' is a matrix* where columns are the input vectors

// After calling rowReduce (original_vectors), identify pivot columns

// The original vectors corresponding to these pivot columns form the basis.

The span is then all linear combinations of these basis vectors.

4. Understanding the span

The span of a set of vectors is the set of all possible linear combinations of those vectors. If we have found a basis, any vector in the span can be expressed as a linear combination of the basis vectors. The dimension of the span is the number of vectors in the basis.

Important considerations

• Floating−point precision: When comparing floating−point numbers (e.g., checking for zero), use a small epsilon value (like 1e−9) instead of direct equality comparison due to potential precision issues.

• Memory management: Remember to malloc and free memory appropriately to prevent memory leaks.

• Error handling: Add checks for malloc failures and other potential errors.