# Solving **A** **x** = **b**

A **basis** β for a vector space *V* is a linearly independent subset of *V*
that generates

or span *V*. If β is a basis for *V*, we also say that elements of β form a basis for
*V*.

This means that every vector from *V* is a finite linear combination of elements from the basis.

Recall that a set of vectors β is said to generate or span a vector space *V* if every element from
*V* can be represented as a linear combination of vectors from β.

Theorem (Kronecker--Capelli Theorem):
A system of linear algebraic equations **A x = b** has a solution if and only if the matrix **A** has the same
rank as the augmented matrix \( \left[ {\bf A} \,|\,{\bf b} \right] . \) ■

**A**. They are equal if and only if

**b**is a linear combination of the columns of the matrix

**A**. The last condition is equivalent to the statement that there exists a vector

**x**such that

**A x = b**. ■

Theorem (Fredholm matrix Theorem):
A system of linear algebraic equations **A x = b** has a solution if and only if **b** is orthogonal to
every solution of the homogeneous equation **z A = 0**, that is, their inner product is zero:
\( {\bf z} \cdot {\bf b} = 0 . \) In other words, the input vector **b** must be
orthogonal to every solution of the homogeneous adjoint equation \( {\bf A}^{\ast} {\bf y} = {\bf 0} , \)
which means that \( {\bf y} \perp {\bf b} \quad \Longleftrightarrow \quad {\bf y} \cdot {\bf b} =0 . \)
■

*Sufficiency Proof:*Let

*r*be the rank of matrix

**A**. We can assume without any loss of generality that the first

*r*rows of the matrix

**A**are linearly independent. Then obviously the first

*r*rows of the augmented matrix will be also linearly independent too. If the

*k*-th row of the matrix

**A**is a linear combination of the first

*r*rows of

**A**, then there exists a nonzero vector

**z**such that

**z A = 0**. According to hypothesis of theorem, \( {\bf z} \cdot {\bf b} = 0 . \) This implies that the

*k*-th row of the augmented matrix \( \left[ {\bf A} \,|\,{\bf b} \right] \) is a linear combination of the first

*r*rows of the augmented matrix. So ranks of

**A**and the augmented matrix are the same. According to Kronecker-Capelli theorem, the linear system of equations

**A x = b**is consistent.

*Necessity Proof:* Suppose that the linear system **A x = b** has a solution. Then for every
\( {\bf z} \in \mathbb{C}^m \) we have the equality

**z A = 0**, then

**z b = 0**. ■

*n*-dimensional real space, and it is called the

**standard basis**. Its dimension is

*n*.

*i*-th row and

*j*-th column. Then the set \( {\bf M}_{i,j} \ : \ 1 \le i \le m , \ 1 \le j \le n \) is a basis for the set of all such real matrices. Its dimension is

*mn*.

*n*. It has dimension

*n*+1. ■

Theorem: Let *V* be a vector space and
\( \beta = \left\{ {\bf u}_1 , {\bf u}_2 , \ldots , {\bf u}_n \right\} \) be a subset of
*V*. Then β is a basis for *V* if and only if each vector *v* in *V* can be uniquely
decomposed into a linear combination of vectors in β, that is, can be uniquely expressed in the form

If the vectors \( \left\{ {\bf u}_1 , {\bf u}_2 , \ldots , {\bf u}_n \right\} \)
form a basis for a vector space *V*, then every vector in *V* can be uniquely expressed in the form

**v**determines a unqiue

*n*-tuple of scalars \( \left[ \alpha_1 , \alpha_2 , \ldots , \alpha_n \right] \) and, conversely, each

*n*-tuple of scalars determines a unique vector \( {\bf v} \in V \) by using the entries of the

*n*-tuple as the coefficients of a linear combination of \( {\bf u}_1 , {\bf u}_2 , \ldots , {\bf u}_n . \) This fact suggests that

*V*is like the

*n*-dimensional vector space \( \mathbb{R}^n , \) where

*n*is the number of vectors in the basis for

*V*.

Theorem: Let *S* be a linearly independent subset of a vector space *V*,
and let **v** be an element of *V* that is not in *S*. Then
\( S \cup \{ {\bf v} \} \) is linearly dependent if and only if **v**
belongs to the span of the set *S*.

Theorem: If a vector space *V* is generated by a finite set *S*, then
some subset of *S* is a basis for *V* ■

A vector space is called **finite-dimensional** if it has a basis consisting of a finite

number of elements. The unique number of elements in each basis for *V* is called

the **dimension** of *V* and is denoted by dim(*V*). A vector space that is not finite-

dimensional is called
**infinite-dimensional**.

The next example demonstrates how *Mathematica* can determine the basis or set of linearly independent
vectors from the given set. Note that basis is not unique and even changing the order of vectors, a software can provide
you another set of linearly independent vectors.

```
MatrixRank[m =
{{1, 2, 0, -3, 1, 0},
{1, 2, 2, -3, 1, 2},
{1, 2, 1, -3, 1, 1},
{3, 6, 1, -9, 4, 3}}]
```

Then each of the following scripts determine a subset of linearly independent vectors:

```
m[[ Flatten[ Position[#, Except[0, _?NumericQ], 1, 1]& /@
```

Last @ QRDecomposition @ Transpose @ m ] ]]

or, using subroutine

```
MinimalSublist[x_List] :=
```

Module[{tm, ntm, ytm, mm = x}, {tm = RowReduce[mm] // Transpose,

ntm = MapIndexed[{#1, #2, Total[#1]} &, tm, {1}],

ytm = Cases[ntm, {___, ___, d_ /; d == 1}]};

Cases[ytm, {b_, {a_}, c_} :> mm[[All, a]]] // Transpose]

we apply it to our set of vectors.
```
m1 = {{1, 2, 0, -3, 1, 0}, {1, 2, 1, -3, 1, 2}, {1, 2, 0, -3, 2,
1}, {3, 6, 1, -9, 4, 3}};
```

MinimalSublist[m1]

`{{1, 1, 1, 3}, {0, 1, 0, 1}, {1, 1, 2, 4}}`

One can use also the standard *Mathematica*command:

**IndependenceTest**. ■