# linalg::matlinsolve

Solving systems of linear equations

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## Syntax

```linalg::matlinsolve(`A`, `b`, <`list`>, `options`)
linalg::matlinsolve(`A`, `B`, `options`)
linalg::matlinsolve(`A`, `options`)
```

## Description

`linalg::matlinsolve(A, b)` computes the general solution of the equation .

`linalg::matlinsolve(A, b)` returns the solution vector of the system if it is a unique solution.

`linalg::matlinsolve(A, b)` returns a list if the system has more than one solution, where is one particular solution, i.e., and form a basis of the kernel of `A`, i.e., the solution space of the homogenous system .

Each solution has the form (rn) with certain scalars s1, …, sr.

A list of n scalars [s1, …, sn] may be passed as the additional parameter `list`. This extracts the solution with from the solution space of the system , where j1, …, jl are the characteristic column indices of `A` (see `linalg::gaussJordan`).

The entries of `list` are converted to elements of the component ring of `A` (an error message is returned if this is not possible).

 Note:   This option should only be used for exact and symbolic computations. In the case that `A` or `b` contains floating-point entries, it should not be used.

If the system has no solution, then the empty list `[]` is returned.

`linalg::matlinsolve(A)` solves the matrix equation , where is the last column of `A` and C is `A` with the last column deleted.

`linalg::matlinsolve(A, B)` returns the solution X of the matrix equation AX = B, if it has exactly one solution. Otherwise the empty list `[]` is returned.

The vector `b` and the matrix `B` respectively, are converted into the domain `Dom::Matrix``(R)`, where `R` is the component ring of `A`. Solution vectors also belong to this domain.

The component ring of `A` must be an integral domain, i.e., a domain of category `Cat::IntegralDomain`.

`linalg::matlinsolve` can compute the general solution for systems with more than one solution only over fields, i.e., component rings of category `Cat::Field`. If in this case the component ring of `A` does not have a canonical representation of the zero element, then it may happen that `linalg::matlinsolve` does not find a basis for the null space. In such a case, a wrong result is returned.

`linalg::matlinsolve` does exploit a sparse structure of `A`. (A matrix is sparse if it has many zero components). See Example 5.

Use the function `numeric::matlinsolve` to solve a linear system numerically.

## Examples

### Example 1

Solve the linear system:

over the reals. First, enter the coefficient matrix and the right side:

```MatR := Dom::Matrix(Dom::Real): A := MatR([[1, 2], [-1, 2]]); b := MatR([1, -1])```

Next, call `linalg::matlinsolve` to solve the system:

`x := linalg::matlinsolve(A, b)`

The system has exactly one solution. The vector `x` satisfies the matrix equation given above:

`A * x`

### Example 2

The system:

does not have a solution over (in fact, over no component domain):

```MatR := Dom::Matrix(Dom::Real): A := MatR([[1, 2], [-1, -2]]): b := MatR([1, 0]): linalg::matlinsolve(A, b)```

### Example 3

Solve the linear system:

over the rational numbers. First, enter the coefficient matrix and the right side:

```MatQ := Dom::Matrix(Dom::Rational): A := MatQ([[1, 1, -4, -7, -6], [0, 1, -3, -5, -7]]); b := MatQ([30, 17])```

Next, call `linalg::matlinsolve` to solve the system:

`sol:= linalg::matlinsolve(A, b)`

The result is to be interpreted as follows: The first vector of the list `sol` is a particular solution of the linear system:

`A * sol[1]`

The second entry of the list contains a basis for the null space of A, i.e., the solution space of the corresponding homogenous system (the kernel of A). The basis returned is given as a list of vectors.

The following input checks this fact by computing the product for each vector of the list `sol[2]`:

`map(sol[2], x -> A * x)`

Any solution of the linear system can be represented as a sum of a particular solution (here: `sol[1]`) and a linear combination of the basis vectors of the kernel of A. Hence the input system has an infinite number of solutions.

For example, another solution of the system is given by:

`x := sol[1] + 1*sol[2][1] + 1/2*sol[2][2] - 2*sol[2][3]`

`A * x`

If you identify the columns of the coefficient matrix A of the linear system with the variables x1, x2, x3, x4, x5, then you see from the general solution that the variables x3, x4, x5 act as free parameters. They can be assigned arbitrary rational values to obtain a unique solution.

By giving a list of values for these variables as a third parameter to `linalg::matlinsolve`, you can select a certain vector from the set of all solutions of the linear system. For example, to select the same vector `x` as chosen in the previous input, enter:

`linalg::matlinsolve(A, b, [0, 0, 1, 1/2, -2])`

If you are only interested in a particular solution and do not need the general solution of the linear system, enter:

`linalg::matlinsolve(A, b, Special)`

This call suppresses the computation of the kernel of A.

### Example 4

If the linear system is given in the form of equations the function `linalg::expr2Matrix` can be used to form the corresponding matrix equation:

```delete x, y, z: Ab := linalg::expr2Matrix( [x + y + z = 6, 2*x + y + 2*z = 10, x + 3*y + z = 10] )```

The result here is the extended coefficient matrix of the input system, that is, the right side vector is the 4th column vector of the matrix `Ab`. Since you did not specify a component ring for this matrix, the standard component ring for matrices, the domain `Dom::ExpressionField``()`, was chosen.

To solve the linear system, call:

`linalg::matlinsolve(Ab)`

The system has an infinite number of solutions. The third variable z acts as a free parameter and therefore can have any (complex) value.

To get the general solution in parameter form, you can use parameters for the variables x, y, z of the input system:

```delete u, v, w: sol := linalg::matlinsolve(Ab, [u, v, w])```

This is possible here because you perform the matrix computations over `Dom::ExpressionField()` which lets you compute with symbolical (arithmetical) expressions.

To select a certain vector from the set of solutions, for example, the solution for w = 1, enter:

`x := subs(sol, w = 1)`

### Example 5

Consider a system of linear equations with a sparse structure, that is, the coefficient matrix has many zero components:

```eqs := {x1 + x5 = 0, x2 - x4 = 1, x3 + 2*x5 = 2, x4 - x5 = -1}: Ab := linalg::expr2Matrix(eqs, [x1, x2, x3, x4, x5])```

`linalg::matlinsolve` exploits the sparsity of the coefficient matrix if it is passed as a matrix of type `Dom::Matrix`. Alternatively, you can use the function `linsolve` which allows sparse input and output via symbolic equations:

`linsolve(eqs)`

You also can use the function `numeric::matlinsolve` with the option `Symbolic` instead of `linalg::matlinsolve`:

```A := linalg::delCol(Ab, 6): b := linalg::col(Ab, 6): numeric::matlinsolve(A, b, Symbolic)```

Note that the function `numeric::matlinsolve` always works over a subfield of the complex numbers and does not let you specify the domain of computation. Without the option `Symbolic`, `numeric::matlinsolve` converts input data to floating-point numbers.

### Example 6

Check whether the matrix equation

has a unique solution over the integers.

Start by entering the coefficient matrix and the right side matrix:

```MatZ := Dom::Matrix(Dom::Integer): A := MatZ([[1, 2], [-2, 3]]); B := MatZ([[4, 2], [6, 3]])```

Next, solve the matrix equation:

`X := linalg::matlinsolve(A, B)`

The equation indeed has a unique solution (otherwise the answer of `linalg::matlinsolve` would be the empty list `[]`). Check the result:

`A * X`

### Example 7

If you use the `Normal` option, `linalg::matlinsolve` calls the `normal` function for final results. This call ensures that `linalg::matlinsolve` returns results in normalized form:

```A := matrix([[1, s], [t, -1]]): b := matrix([s + 1, t - 1]): x := linalg::matlinsolve(A, b)```

If you specify `Normal = FALSE`, `linalg::matlinsolve` does not call `normal` for the final result:

`x := linalg::matlinsolve(A, b, Normal = FALSE)`

### Example 8

Solve this system:

```A := matrix([[1, s], [1, t]]): b := matrix([1, 1]):```
`linalg::matlinsolve(A, b)`

Note that more solutions exist for `t = s`. `linalg::matlinsolve` omits these solutions because it makes some additional assumptions on symbolic parameters of this system. To see the assumptions that `linalg::matlinsolve` made while solving this system, use the `ShowAssumptions` option:

`linalg::matlinsolve(A, b, ShowAssumptions)`

## Parameters

 `A` m×n matrix of a domain of category `Cat::Matrix` `B` m×k matrix of a domain of category `Cat::Matrix` `b` m-dimensional column vector, i.e., a m×1 matrix of a domain of category `Cat::Matrix` `list` List of n elements of the component ring of `A`

## Options

 `Normal` Option, specified as `Normal = b` Return normalized results. The value `b` must be `TRUE` or `FALSE`. By default, `Normal = TRUE`, meaning that `linalg::matlinsolve` guarantees normalization of the returned results. Normalizing results can be computationally expensive. By default, `linalg::matlinsolve` calls `normal` before returning results. This additional internal call ensures that the final result is normalized. This call can be computationally expensive. This option affects the output only if the solution contains variables or exact expressions, such as `sqrt(5)` or `sin(PI/7)`. To avoid this additional call, specify `Normal = FALSE`. In this case, `linalg::matlinsolve` also can return normalized results, but does not guarantee such normalization. See Example 7. `ShowAssumptions` Return information about internal assumptions that `linalg::matlinsolve` made on symbolic parameters in `eqs`. With `ShowAssumptions`, `linalg::matlinsolve` returns a list `[S, KernelBasis, Constraints, Pivots]`. The lists `Constraints` and `Pivots` contain equations and inequalities involving symbolic parameters in `A` and `b` (or `B`). Internally, these were assumed to hold true when solving the system. See Example 8. When Gaussian elimination produces an equation ```0 = c``` with nonzero `c`, `linalg::matlinsolve` without `ShowAssumptions` returns `[]`. If `c` involves symbolic parameters, try using `linalg::matlinsolve` with `ShowAssumptions` to solve such systems. If the system is solvable, you will get the solution. In this case, an equation `0 = c` is returned in the `Constraints` list. If the system is not solvable, `linalg::matlinsolve` with `ShowAssumptions` returns ```[[], [], [], []]```. `Special` Only one particular solution `w` of the system is returned. This supresses the computation of a basis for the kernel of `A`. `Unique` Checks whether the system has a unique solution and returns it. The return value `NIL` means that the system has more than one solution.

## Return Values

Without `ShowAssumptions`, `linalg::matlinsolve` can return a vector or a list `[S, KernelBasis]` (possibly empty), where `S` is a solution vector and `KernelBasis` is a list of basis vectors for the kernel of `A`. It also can return a matrix or the value `NIL`.

The matrix and the vectors, respectively, are of the domain type `Dom::Matrix(R)`, where `R` is the component ring of `A`.

With `ShowAssumptions`, `linalg::matlinsolve` returns a list `[S, KernelBasis, Constraints, Pivots]`. The lists `Constraints` and `Pivots` contain equations and inequalities involving symbolic parameters in `A` and `b` (or `B`). Internally, these were assumed to hold true when solving the system. If the system is not solvable, `linalg::matlinsolve` with `ShowAssumptions` returns ```[[], [], [], []]```.

## Algorithms

Let A be an m×n matrix with components from a field F and an m-dimensional vector over F. Let be the extended coefficient matrix of the linear system .

Then the following holds:

• The linear system has a solution, if and only if .

• It has exactly one solution, if and only if .

• If is a solution of the system and a basis of the kernel of A, then

is the set of all solutions of the linear system , the general solution of the (inhomogeneus) linear system.

The kernel of the matrixA is defined as:

.

The kernel of A is a vector space over F of dimension n - rank(A).