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).

Was this topic helpful?