Lesson 1. Basic algorithms.

Goals. The first lesson is devoted to recall some algebraic concepts and algorithms widely used in the forthcoming lessons, all of them crutial to coordinate geometry.
1.1 Operations on matrices. In this section we recall some basic operations that can be performed on matrices, namely the addition of two matrices,the scalar multiplication of a matrix by a number and the multiplication of two matrices. The inverse matrix of a given one is presented later on.

Sum. Matrices are added in the same way as vectors, namely entry by entry.
Example 1
Only matrices having the same dimensions, that is, the same number of rows and columns, can be added.
Scalar multiplication. The scalar multiplication of a matrix by a real number is also performed entry by entry.
Example 2

Multiplication of matrices. We perform the multiplication of two matrices by doing the escalar product of all the rows in the first matrix by all the columns in the second one.
Example 3
In order to calculate the product of two matrices, the number of columns of the first one must equal the number of rows of the second one.
The result will be a matrix having as many rows as the first matrix and as many columns as the second matrix.

dim(A) = 2 x 2, dim(B) = 3 x 2   >>>   dim(AB) = 2 x 3
dim(A) = m x n, dim(B) = n x p   >>>   dim(AB) = m x p

exercise 1 problem 1.1
exercise 2 problem 1.2 1.2 Determinants. The determinant of an squared matrix is a numeric value computed from the entries of the matrix. It provides information about the linear dependencies among its rows or columns.
On the other hand, the unsigned determinant is also the volume of the solid limited by the rows (alternatively, columns) of the matrix, when we think of them as a set of vectors with common origin.
Furthermore, the sign of the determinant informs about the particular orientation induced by a vectorial basis on a geometrical space.

Determinat computing. The determinant of an squared nxn matrix is the (signed) sum of all possible products of n different entries of the matrix, that involve exactly only one entry per row and one entry per column

Example 4 determinant 2x2.
Example 5 determinant 3x3 (estrella).
Example 6 determinant nxn (desenvolupant per files o columnes).
The Gauss-Jordan algorithm can be also used to calculate the determinant of a given matrix, although there could be some side effects (be careful!).

Interpretació geomètrica. The determinant of two 2-dimensional vectors (i.e. an squared 2x2 matrix), computes the area of the paralelogram that has those particulars vectors as edges. why?

In a similar way, the determinant of three 3-dimensional vectors computes the volume.

As a consequencia, the determinant of two parallel vectors or three coplanary vectors is null.

More generally, the determinant of n linealment dependent vectors is also null.

exercise 3 problem 1.5 1.3 The rank of a matrix. We define the rank of a matrix to be its number of linearly independent rows (or columns) Two different approachers can be followed in order to compute the rank of a given matrix A, which are based on either the notion of determinant, or the Gauss-Jordan algorithm.

Computing the rank The determinant-based approach consists in finding the biggest squared submatrix of A such that its determinant is not zero.

Precisely, a submatrix of A means a smaller matrix obtained from A by deleting some of the columns and rows.

Example 7

is a 2x2 submatrix with null determinant.
is a 2x2 submatrix with non null determinant from the same matrix.
This is NOT a submatrix, because 1 and 2 do not share the same row.
It is not necessary, in order to compute the rank of a matrix, to consider all of the possible submatrices. Only a suitably chosen sequence of incresing submatrices is needed to that purpose, as it is shown in the next example.
Example 8 The rank of the matrix in the previous example is 3. Next figure shows a possible sequence of submatrices with non null determinant leading to that fact.

exercise 4 problem 1.6 1.4 Systems of linear equations. A system of linear equations expresses linear dependencies among the involved variables ( the so-called unknowns). Solving the system is the process of finding the possible values of the unknowns such that satisfy all the equations in the system.
By adding equations to a system we can make it too restrictive in order to have any solution at all. Conversely, a system with too few equations tend to have many (infinite) solutions. The reader should take this statement as a rule of thumb rather than as an exact piece of information. In fact, it is the linear dependencies between equations, rather than its number, what determines the kind of solutions we can expect.

Some easy examples.
Problem 9   Find out two numbers such that the first one plus the double of the second equals 6.
Answer.   Lets represent the unknown quantities by two variables, x and y, and lets translate the stated restriction into mathematical language by writing the equation: x + 2y = 6 .
At a glance, we can find many pairs of values satisfying the required condition, e.g. x=2 and y=2, or x=0 and y=3. Therefore, the solution is not unique.

Problem 10   Find out two numbers such that any one of them plus the double of the other equals 6.
Answer.   In this case, two different constrains are to be imposed leading to a two different equations. As before, we have x + 2y = 6 , but also y + 2x = 6 . The unique solution for that system is x = y = 2 .

Problem 11   Find out two numbers such that any one of them plus the double of the other equals 6, and their product equals 8.
Answer   Three different conditions are to be translated into equations in the present case, which are: x + 2y = 6 , y + 2x = 6 and xy = 8 . Therefore, the number of equations exceedes the number of unknowns. Although this fact in itself does not lead to any particular conclusion, in many cases it goes together with the lack of solutions for the system. That is exactly the case in the present example. There are no values of x and y satisfying all the equations simultaneously. In addition to that, note that the system is NOT linear, as the third equation includes a product of two unknowns. So Gaussian reduction can not be used to solve the system.

Matrix notation for the linear systems of equations.
As it has been said before, a system of equations is a collection of equations that have to be satisfied simultaneously by a set of numeric variables, the unknowns.
Furthermore, a system of equations is called linear if the equations involve only sums of variables (unknowns) multiplied by numbers (escalars) and independent standing alone numerical constants.
Every system of linear equations can be written as a product of a suitably chosen matrix A with constant entries Ax = b where on:
   
    • A is called the matrix of the system
    • x is the unknowns vector
    • b is called the independent terms vector
Sometimes, the unknowns vector is omited and the previous expression Ax = b becomes (A | b) .

example 12   Going back to the three previous examples, matricial notation looks like:
equations
matrices product
compact expression
It is not linear. Therefore,
it cannot be expressed as a product of matrices. 		None.

Resolució de sistemes lineals. El mètode de Gauss. Consisteix en fer zeros a sota de la diagonal principal de la matriu.
exercici 5   problema 1.8

Discussió de sistemes. No cal aplicar el mètode de Gauss (o qualsevol altre) per a saber si un sistema té o no solució, o si aquesta solució serà única.

Teorema de Rouché-Frobënius
El sistema Ax=b és compatible (o sigui, té solució) si i només si rang(A)=rang(A,b).

A més, la solució depèn de m=n-rang(A) paràmetres, on n representa el nombre d'incògnites.

exercici 6   problema 1.11
1.5 The inverse of a matrix. Inverting a matrix A is the process of computing another matrix usually denoted by A-1, such that their product is the identity. Such a matrix does not always exist.
Inverse matrices are closely related with the solving of linear equations.

Preliminary examples.

exemple 13   The ineverse of     is   .
To check that, we only need to compute the product of both matrices:;

exemple 14   The inverse of     does not exist. This is because the result of multiplying A by any other matrix always has a zero row.

Properties.
      • Only square matrix might have inverses.
    • If A-1 is the inverse of A, then AA-1 = A-1A = Id
    • The inverse of a matrix A is unique. Therefore if AB=Id and AC=Id for some matrices B and C, then B=C.
    • Only matrices with non nul determinanthave inverse.

    Càlcul de la inversa. There are two practical methods for finding A-1, each one based on a different method for solving systems of linear equations:
    1. Gaussian elimination.
    2. Cramer's Rule.

    example 15   The Gaussian approach.In order to compute the inverse of     lets write first the 2x4 matrix:

    We apply now row operations in such a way as to reduce A (the left side) to I, the identity matrix. We will end up with:

    where the right side is exactly the inverse of A,  
    exercise 7   problem 1.9

    Inverse computing as system solving. Computing the inverse is nothing but solving a set of systems of linear equations, all of them sharing the same left side matrix (A, in fact) but different independent right side vectors (namely, the columns of the identity matrix I).

    example 16   Let us effectively compute the inverse of A in the previous example. We are looking for a matrix B such that AB=I.
    The product of matrices above leads to two different systems of linear equations
    that we now rewrite as:
    Only the left side of the matrix has an effect on the steps we follow when doing Gaussian elimination. Being both left sides identical, we can write the two systems in a compact way:
    and solve them simultaneously.
    exercise 8   problem 1.10