Algorithm for matrix-vector multiplication. Matrix multiplication: examples, algorithm of actions, properties of the product

In the MatLab system, it is quite simple to perform mathematical operations on matrices and vectors. Let us first consider simple operations of addition and multiplication of matrices and vectors. Let two vectors be given

a = ; % row vector
b = ; % column vector

then the multiplication of these two vectors can be written as follows

c = a*b; % c=1+2+3+4+5=16
d = b*a; % d – matrix of 5x5 elements

In accordance with operations on vectors, multiplying a row vector by a column vector gives a number, and multiplying a column vector by a row vector gives a two-dimensional matrix, which is the result of the calculations in the above example, i.e.

Addition and subtraction of two vectors is written as follows:

a1 = ;
a2 = ;
c = a1+a2; % c = ;
c = a2-a1; % c = ;

Note that addition and subtraction operations can be performed between two column vectors or two row vectors. Otherwise, MatLab will display an error message, because Vectors of different types cannot be added. This is the case with all illegal arithmetic operations: if they cannot be calculated, MatLab will report an error and the program will terminate on the corresponding line.

Multiplication and addition operations between matrices are performed in a similar way:

A = ;
B = ones(3);
C = A+B; % addition of two matrices of the same size
D = A+5; % addition of matrix and number
E = A*B; % multiplication of matrix A by B
F = B*A; % multiplication of matrix B by A
G = 5*A; % multiplying a matrix by a number

The operations of calculating the inverse matrix, as well as transposing matrices and vectors, are written as follows:

a = ; % row vector
b = a’; % column vector formed by
% by transposing the row vector a.
A = ; % 3x3 element matrix
B = a*A; %B = – row vector
C = A*b; %C = – column vector
D = a*A*a’; % D = 45 – number, sum of elements of matrix A
E = A'; % E – transposed matrix A
F = inv(A); % F – inverse matrix A
G = A^-1; % G – inverse matrix A

From the above example it is clear that the operation of transposing matrices and vectors is indicated by the symbol ‘ (apostrophe), which is placed after the name of the vector or matrix. Calculating the inverse of a matrix can be done by calling the inv() function or by raising the matrix to the -1 power. The result in both cases will be the same, and two methods of calculation are made for ease of use when implementing different algorithms.

If in the process of calculations it is necessary to multiply, divide or raise elements of a vector or matrix element-by-element, then the following operators are used for this:

.* - element-wise multiplication;
./ and.\ - element-by-element divisions;
.^ - element-wise exponentiation.

Let's look at how these operators work using the following example.

a = ; % row vector
b = ; % row vector
c = a.*b; %c=
A = ones(3); % 3x3 matrix consisting of ones
B = ; % 3x3 matrix
C = A.*B; % 3x3 matrix consisting of
D = A./B; % 3x3 matrix consisting of
E = A.\B; % 3x3 matrix consisting of
F = A.^2; % squaring the elements of matrix A

At the end of this section, we will consider several functions useful when working with vectors and matrices.

To find the maximum value of a vector element, use the standard max() function, which returns the found maximum value of the element and its position (index):

a = ;
= max(a); % v = 6, i = 2;

v = max(a); % v = 6;

The following example shows two different ways to call the max() function. In the first case, both the maximum value of the element and its index in the vector are determined, and in the second - only the maximum value of the element.

In the case of matrices, this function determines the maximum values ​​​​standing in the columns, as shown in the example below:

A = ;
= max(A); %V=,I=
V = max(A); %V=

The full syntax of the max() function can be found by typing the command in the MatLab command window

help<название функции>

The min() function works in a similar way, which determines the minimum value of an element of a vector or matrix and its index.

Another useful function for working with matrices and vectors is the sum() function, which calculates the sum of the values ​​of the elements of a vector or matrix columns:

a = ;
s = sum(a); % s = 3+5+4+2+1=15
A = ;
S1 = sum(A); %S1=
S2 = sum(sum(A)); % S2=39

When calculating the sum S2, the sum of the values ​​of the elements of matrix A is first calculated in columns, and then in rows. As a result, variable S2 contains the sum of the values ​​of all elements of matrix A.

To sort the element values ​​of a vector or matrix in ascending or descending order, use the sort() function as follows:

a = ;

b1 = sort(a); %b1=
b2 = sort(a, ‘descend’); %b2=
b3 = sort(a, ‘ascend’); %b3=

for matrices

A = ;
B1 = sort(A); %B1=
B2 = sort(A, 'descend'); %B2=

In many practical problems, you often need to find a specific element in a vector or matrix. This can be done using the standard find() function, which takes as an argument a condition according to which the required elements are found, for example:

a = ;
b1 = find(a == 2); % b1 = 4 – index of element 2
b2 = find(a ~= 2); % b2 = – indexes without 2
b3 = find(a > 3); % b3 =

In the example given, the symbol ‘==’ means checking for equality, and the symbol ‘~=’ checks for inequality of the values ​​of the elements of vector a. These operators will be described in more detail in the section Conditional Operators.

Another useful function for working with vectors and matrices is the mean() function for calculating the arithmetic mean, which works as follows:

a = ;
m = mean(a); % m = 3
A = ;
M1 = mean(A); % M1 =
M2 = mean(mean(A)); % M2 = 4.333

Matrix product (C = AB) is an operation only for matched matrices A and B, in which the number of columns of matrix A is equal to the number of rows of matrix B:

C ⏟ m × n = A ⏟ m × p × B ⏟ p × n

Example 1

Given matrices:

• A = a (i j) of dimensions m × n;
• B = b (i j) sizes p × n

Matrix C, the elements c i j of which are calculated using the following formula:

c i j = a i 1 × b 1 j + a i 2 × b 2 j + . . . + a i p × b p j , i = 1 , . . . m, j = 1, . . . m

Example 2

Let's calculate the products AB=BA:

A = 1 2 1 0 1 2 , B = 1 0 0 1 1 1

Solution using the matrix multiplication rule:

A ⏟ 2 × 3 × B ⏟ 3 × 2 = 1 2 1 0 1 2 × 1 0 0 1 1 1 = 1 × 1 + 2 × 0 + 1 × 1 1 × 0 + 2 × 1 + 1 × 1 0 × 1 + 1 × 0 + 2 × 1 0 × 0 + 1 × 1 + 2 × 1 = = 2 3 2 3 ⏟ 2 × 2

B ⏟ 3 × 2 × A ⏟ 2 × 3 = 1 0 0 1 1 1 × 1 2 1 0 1 2 = 1 × 1 + 0 × 0 1 × 2 + 0 × 1 1 × 1 + 0 × 2 0 × 1 + 1 × 0 0 × 2 + 1 × 1 0 × 1 + 1 × 2 1 × 1 + 1 × 0 1 × 2 + 1 × 1 1 × 1 + 1 × 2 = 1 2 1 0 1 2 1 3 3 ⏟ 3×3

The product A B and BA A are found, but they are matrices of different sizes: A B is not equal to BA A.

Properties of matrix multiplication

Properties of matrix multiplication:

• (A B) C = A (B C) - associativity of matrix multiplication;
• A (B + C) = A B + A C - distributivity of multiplication;
• (A + B) C = A C + B C - distributivity of multiplication;
• λ (A B) = (λ A) B

Let's check property No. 1: (A B) C = A (B C) :

(A × B) × A = 1 2 3 4 × 5 6 7 8 × 1 0 0 2 = 19 22 43 50 × 1 0 0 2 = 19 44 43 100,

A (B × C) = 1 2 3 4 × 5 6 7 8 1 0 0 2 = 1 2 3 4 × 5 12 7 16 = 19 44 43 100.

Example 2

Let's check property No. 2: A (B + C) = A B + A C:

A × (B + C) = 1 2 3 4 × 5 6 7 8 + 1 0 0 2 = 1 2 3 4 × 6 6 7 10 = 20 26 46 58,

A B + A C = 1 2 3 4 × 5 6 7 8 + 1 2 3 4 × 1 0 0 2 = 19 22 43 50 + 1 4 3 8 = 20 26 46 58.

Product of three matrices

The product of three matrices A B C is calculated in 2 ways:

• find A B and multiply by C: (A B) C;
• or first find B C, and then multiply A (B C).

Multiply matrices in 2 ways:

4 3 7 5 × - 28 93 38 - 126 × 7 3 2 1

Algorithm of actions:

• find the product of 2 matrices;
• then again find the product of 2 matrices.

1). A B = 4 3 7 5 × - 28 93 38 - 126 = 4 (- 28) + 3 × 38 4 × 93 + 3 (- 126) 7 (- 28) + 5 × 38 7 × 93 + 5 (- 126 ) = 2 - 6 - 6 21

2). A B C = (A B) C = 2 - 6 - 6 21 7 3 2 1 = 2 × 7 - 6 × 2 2 × 3 - 6 × 1 - 6 × 7 + 21 × 2 - 6 × 3 + 21 × 1 = 2 0 0 3 .

We use the formula A B C = (A B) C:

1). B C = - 28 93 38 - 126 7 3 2 1 = - 28 × 7 + 93 × 2 - 28 × 3 + 93 × 1 38 × 7 - 126 × 2 38 × 3 - 126 × 1 = - 10 9 14 - 12

2). A B C = (A B) C = 7 3 2 1 - 10 9 14 - 12 = 4 (- 10) + 3 × 14 4 × 9 + 3 (- 12) 7 (- 10) + 5 × 14 7 × 9 + 5 (- 12) = 2 0 0 3

Answer: 4 3 7 5 - 28 93 38 - 126 7 3 2 1 = 2 0 0 3

Multiplying a matrix by a number

The product of matrix A by number k is matrix B = A k of the same size, which is obtained from the original one by multiplying all its elements by a given number:

b i, j = k × a i, j

Properties of multiplying a matrix by a number:

• 1 × A = A
• 0 × A = zero matrix
• k (A + B) = k A + k B
• (k + n) A = k A + n A
• (k × n) × A = k (n × A)

Let's find the product of the matrix A = 4 2 9 0 by 5.

5 A = 5 4 2 9 0 5 × 4 5 × 2 5 × 9 5 × 0 = 20 10 45 0

Multiplying a matrix by a vector

To find the product of a matrix and a vector, you need to multiply using the “row by column” rule:

• if you multiply a matrix by a column vector, the number of columns in the matrix must match the number of rows in the column vector;
• The result of multiplying a column vector is just a column vector:

A B = a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋯ ⋯ ⋯ ⋯ a m 1 a m 2 ⋯ a m n b 1 b 2 ⋯ b 1 n = a 11 × b 1 + a 12 × b 2 + ⋯ + a 1 n × b n a 21 × b 1 + a 22 × b 2 + ⋯ + a 2 n × b n ⋯ ⋯ ⋯ ⋯ a m 1 × b 1 + a m 2 × b 2 + ⋯ + a m n × b n = c 1 s 2 ⋯ s 1 m

• if you multiply a matrix by a row vector, then the matrix being multiplied must be exclusively a column vector, and the number of columns must match the number of columns in the row vector:

A B = a a ⋯ a b b ⋯ b = a 1 × b 1 a 1 × b 2 ⋯ a 1 × b n a 2 × b 1 a 2 × b 2 ⋯ a 2 × b n ⋯ ⋯ ⋯ ⋯ a n × b 1 a n × b 2 ⋯ a n × b n = c 11 c 12 ⋯ c 1 n c 21 c 22 ⋯ c 2 n ⋯ ⋯ ⋯ ⋯ c n 1 c n 2 ⋯ c n n

Example 5

Let's find the product of matrix A and column vector B:

A B = 2 4 0 - 2 1 3 - 1 0 1 1 2 - 1 = 2 × 1 + 4 × 2 + 0 × (- 1) - 2 × 1 + 1 × 2 + 3 × (- 1) - 1 × 1 + 0 × 2 + 1 × (- 1) = 2 + 8 + 0 - 2 + 2 - 3 - 1 + 0 - 1 = 10 - 3 - 2

Example 6

Let's find the product of matrix A and row vector B:

A = 3 2 0 - 1 , B = - 1 1 0 2

A B = 3 2 0 1 × - 1 1 0 2 = 3 × (- 1) 3 × 1 3 × 0 3 × 2 2 × (- 1) 2 × 1 2 × 0 2 × 2 0 × (- 1) 0 × 1 0 × 0 0 × 2 1 × (- 1) 1 × 1 1 × 0 1 × 2 = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

Answer: A B = - 3 3 0 6 - 2 2 0 4 0 0 0 0 - 1 1 0 2

If you notice an error in the text, please highlight it and press Ctrl+Enter

Each vector can be thought of as a single-column or single-row matrix. We will call a single-column matrix a column vector, and a single-row matrix a row vector.

If A is a matrix of size m*n, then the column vector b has size n, and the row vector b has size m.

Thus, to multiply a matrix by a vector, we must consider the vector as a column vector. When multiplying a vector by a matrix, it must be treated as a row vector.

Multiply matrix

to a complex vector

We get the result

As you can see, with the vector dimension unchanged, we can have two solutions.

I would like to draw your attention to the fact that the matrix in the first and second versions, despite the same values, are completely different (have different dimensions)

In the first case, the vector is considered as a column and then it is necessary multiply matrix by vector, and in the second case we have a row vector and then we have product of a vector and a matrix.

This bot also multiplies vectors and matrices that have complex values. Based on a more complete calculator: Matrix multiplication with complex values ​​online

Properties of matrix-vector multiplication

Matrix

Vector column

Row vector

Arbitrary number

1. The product of a matrix by the sum of column vectors is equal to the sum of the products of the matrix by each of the vectors

2. The product of the sum of row vectors and the matrix is ​​equal to the sum of the products of vectors and the matrix

3. The common factor of a vector can be moved beyond the product of a matrix by a vector/vector by a matrix

4. The product of a row vector and the product of a matrix and a column vector is equivalent to the product of the product of a row vector and a matrix and a column vector.

Lecture 6. Parallel numerical algorithms for solving typical problems of computational mathematics: matrix multiplication.

Multiplying a matrix by a vector. Achieving the highest possible performance. Exploiting mid-level parallelism. Organization of parallel computing at p = n. Use of a limited set of processors. Matrix multiplication. Macro-operational analysis of problem solving algorithms. Organization of parallelism based on data sharing.

Multiplying a matrix by a vector

The problem of multiplying a matrix by a vector is defined by the relations

Thus, obtaining the resulting vector involves repeating similar operations of multiplying the rows of the matrix and the vector. Obtaining each such operation involves element-wise multiplication of the elements of a row of a matrix and a vector and the subsequent summation of the resulting products. The total number of required scalar operations is estimated by the quantity

As follows from the actions performed when multiplying a matrix and a vector, parallel methods for solving the problem can be obtained based on parallel summation algorithms (see paragraph 4.1). In this section, the analysis of parallelization methods will be supplemented by consideration of issues of organizing parallel computing depending on the number of processors available for use. In addition, using the example of the problem of multiplying a matrix by a vector, attention will be drawn to the need to select the most suitable topology of the computing system (existing communication channels between processors) to reduce costs for organizing interprocessor interaction.

Achieving the highest possible performance ()

Let us analyze information dependencies in the matrix-vector multiplication algorithm to select possible parallelization methods. As you can see, the operations of multiplying individual rows of a matrix by a vector performed during calculations are independent and can be performed in parallel;

Multiplying each row by a vector involves independent element-wise multiplication operations and can also be performed in parallel;

The summation of the resulting products in each operation of multiplying a matrix row by a vector can be performed using one of the previously considered variants of the summation algorithm (sequential algorithm, conventional and modified cascade schemes).

Thus, the maximum required number of processors is determined by the value

The use of such a number of processors can be represented as follows. Many processors are divided into groups

,

each of which represents a set of processors for performing the operation of multiplying an individual row of a matrix by a vector. At the beginning of calculations, a matrix row element and a corresponding vector element are sent to each processor in the group. Next, each processor performs a multiplication operation. Subsequent calculations are then performed using a cascade summation scheme. For illustration in Fig. 6.1 shows the computational scheme for the processors of a group with a matrix dimension of .

Rice. 6.1. Computational scheme for multiplying a matrix row by a vector

The execution time of a parallel algorithm when using processors is determined by the execution time of the parallel multiplication operation and the execution time of the cascade circuit

As a result, the efficiency indicators of the algorithm are determined by the following relationships:

, ,

For the problem of matrix-vector multiplication under consideration, the most suitable topologies are structures that provide fast data transmission (paths of unit length) in a cascade summation circuit (see Fig. 4.5). Such topologies are a structure with a complete system of connections ( complete graph) And hypercube. Other topologies lead to increased communication time due to longer data transfer routes. Thus, with a linear ordering of processors with a system of connections only with the nearest neighbors on the left and right ( ruler or ring) for a cascade scheme, the length of the transmission path of each received partial sum at iteration , , is equal to . If we assume that data transmission along a path length in topologies with a linear structure requires data transmission operations, the total number of parallel operations (total duration of paths) of data transmission is determined by the value

(excluding data transfers for initial loading of processors).

Application of a computing system with a rectangular topology two-dimensional lattice size leads to a simple and clear interpretation of the calculations being performed (the structure of the network corresponds to the structure of the processed data). For such a topology, it is most advisable to place the matrix rows along the horizontal grids; in this case, the elements of the vector must be distributed along the verticals of the computing system. Calculations with this arrangement of data can be carried out in parallel along the grid lines; as a result, the total number of data transfers matches the results for ruler().

Communication actions performed when solving a given task consist of transferring data between pairs of MCS processors. A detailed analysis of the duration of implementation of such operations is carried out in paragraph 3.3.

4. Recommendations for implementing a parallel algorithm. When implementing a parallel algorithm, it is advisable to highlight the initial stage of loading the used processors with initial data. Most simply, such initialization is provided with a topology of a computer system with a topology in the form complete graph(download is provided using one parallel data transfer operation). When organizing multiple processors in the form hypercube It may be useful to have two-level control of the bootstrap process, in which the central control processor ensures that the matrix and vector rows are sent to the control processors of the processor groups, which, in turn, send the elements of the matrix and vector rows to the executive processors. For topologies in the form rulers or rings requires sequential data transfer operations with a successively decreasing amount of data transferred from to elements.

Using mid-level parallelism()

1. Choosing a parallel computing method. When the available number of used processors () decreases, the usual cascade summation scheme when performing operations of multiplying matrix rows by vector becomes inapplicable. To simplify the presentation of the material, let us assume and use a modified cascade scheme. The initial load of each processor in this case increases and the processor is loaded () by parts of the rows of the matrix and vector. The execution time of the operation of multiplying a matrix by a vector can be estimated as

When using the number of processors required to implement the modified cascade scheme, i.e. at , this expression gives an estimate of the execution time (at ).

When the number of processors is , when the execution time of the algorithm is estimated as , a new scheme for parallel execution of calculations can be proposed, in which for each iteration of the cascade summation the non-overlapping sets of processors. With this approach, the available number of processors turns out to be sufficient to implement only one operation of multiplying a matrix row and a vector. In addition, when performing the next iteration of cascade summation, the processors responsible for executing all previous iterations are free. However, this disadvantage of the proposed approach can be turned into an advantage by using idle processors to process the next rows of the matrix. As a result, the following scheme can be formed conveyor performing matrix and vector multiplication:

A set of processors is divided into disjoint processor groups

,

in this case, the group , , consists of processors and is used to perform iterations of the cascade algorithm (the group is used to implement element-wise multiplication); total number of processors;

Initialization of calculations consists of element-by-element loading of the processors of the group with the values ​​of 1 row of the matrix and vector; after the initial loading, a parallel operation of element-wise multiplication and subsequent implementation of the usual cascaded summation circuit is performed;

When performing calculations, each time after the completion of an element-wise multiplication operation, the processors of the group are loaded with elements of the next row of the matrix and the calculation process is initiated for the newly loaded data.

As a result of applying the described algorithm, many processors implement a pipeline for performing the operation of multiplying a matrix row by a vector. On such a conveyor there can simultaneously be several separate rows of the matrix at different stages of processing. So, for example, after element-wise multiplication of the elements of the first row and the vector, the processors of the group will perform the first iteration of the cascade algorithm for the first row of the matrix, and the processors of the group will perform element-wise multiplication of the values ​​of the second row of the matrix, etc. For illustration in Fig. 6.2 shows the situation of the calculation process after 2 iterations of the pipeline at .

Rice. 6.2. State of the pipeline for the operation of multiplying a matrix row by a vector after completing 2 iterations

2. Evaluation of algorithm performance indicators. The multiplication of the first row by vector according to the cascade scheme will be completed as usual after the execution of () parallel operations. For other rows - in accordance with the pipeline scheme of organizing calculations - the appearance of the multiplication results of each next row will occur after the completion of each subsequent iteration of the pipeline. As a result, the total execution time of the matrix-vector multiplication operation can be expressed as

This estimate is slightly longer than the execution time of the parallel algorithm described in the previous paragraph (), however, the newly proposed method requires less transmitted data (the vector is sent only once). In addition, the use of a pipeline scheme results in the earlier appearance of some of the computational results (which can be useful in a number of data processing situations).

As a result, the efficiency indicators of the algorithm are determined by the following relations:

3. Selecting the topology of the computing system. The appropriate topology of a computing system is completely determined by the computing circuit - this is a complete binary tree height The number of data transfers with such a network topology is determined by the total number of iterations performed by the pipeline, i.e.

.

Initialization of calculations begins with the leaves of the tree, the summation results are accumulated in the root processor.

The analysis of the complexity of performed communication actions for computing systems with other interprocessor communication topologies is supposed to be carried out as an independent task (see also clause 3.4).

Organization of parallel computing in

1. Choosing a parallel computing method. When using processors to multiply a matrix by a vector, the parallel row-by-row multiplication algorithm previously discussed in the manual can be used, in which the rows of the matrix are distributed among the processors row-by-row and each processor implements the operation of multiplying any individual row of the matrix by a vector. Another possible way to organize parallel computing could be to build pipeline circuit for the operation of multiplying a matrix row by a vector(scalar product of vectors) by arranging all available processors in a linear sequence ( rulers).

Such a calculation scheme can be defined as follows. Let's imagine the set of processors as a linear sequence (see Fig. 4.7):

Each processor, , is used to multiply the elements of a matrix column and a vector element. The calculations performed on each processor , , are as follows:

The next element of the matrix column is requested;

The elements and are multiplied;

The result of the previous processor's calculations is requested;

The values ​​are added;

The resulting result is sent to the next processor.

Rice. 6.3. State of the linear pipeline for the operation of multiplying a matrix row by a vector after performing two iterations

When initializing the described scheme, you must perform a number of additional actions:

When performing the first iteration, each processor additionally requests an element of the vector;

To synchronize calculations (when performing the next iteration of the circuit, the calculation result of the previous processor is requested) at the initialization stage, the processor, , performs () a wait loop.

In addition, for the homogeneity of the described circuit for the first processor, which does not have a previous processor, it is advisable to introduce an empty addition operation ( ).

For illustration in Fig. Figure 6.3 shows the state of the computation process after the second iteration of the pipeline at .

2. Evaluation of algorithm performance indicators. The multiplication of the first row by the vector according to the described pipeline scheme will be completed after the execution of () parallel operations. The result of multiplying the following lines will occur after the completion of each next iteration of the pipeline (recall that the iteration of each processor includes the execution of multiplication and addition operations). As a result, the total execution time of a matrix-vector multiplication operation can be expressed as:

This estimate is also greater than the minimum possible execution time of the parallel algorithm at . The usefulness of using a pipeline computing scheme is, as noted in the previous paragraph, in reducing the amount of transmitted data and in the earlier appearance of some of the calculation results.

The efficiency indicators of this computational scheme are determined by the relations:

, ,

3. Selecting the topology of the computing system. The necessary topology of the computing system for executing the described algorithm is uniquely determined by the proposed computing scheme - this is a linearly ordered set of processors ( ruler).

Using a limited set of processors ()

1. Choosing a parallel computing method. By reducing the number of processors to a value, a parallel computing scheme for matrix-vector multiplication can be obtained by adapting the row-by-row multiplication algorithm. In this case, the cascade circuit for summing the results of element-wise multiplication degenerates and the operation of multiplying a matrix row by a vector is completely performed on a single processor. The computational scheme obtained with this approach can be specified as follows:

A vector and matrix rows are sent to each of the available processors;

Performing a matrix-vector row multiplication operation is performed using a conventional sequential algorithm.

It should be noted that the matrix size may not be a multiple of the number of processors and then the matrix rows cannot be divided equally between processors. In these situations, you can deviate from the requirement of uniform loading of processors and, in order to obtain a simpler computational scheme, accept the rule that data is placed on processors only row by row (i.e., elements of one row of the matrix cannot be divided among several processors). An unequal number of rows leads to different computational load on processors; Thus, the completion of calculations (the total duration of solving the problem) will be determined by the operating time of the most loaded processor (in this case, part of this total time, individual processors may be idle due to the exhaustion of their share of calculations). The uneven load of processors reduces the efficiency of using MCS and, as a result of considering this example, we can conclude that balancing problem

3. Selecting the topology of the computing system. In accordance with the nature of the interprocessor interactions performed in the proposed computing scheme, the organization of processors in the form of stars(see Fig. 1.1). A control processor of such a topology can be used to load computing processors with initial data and to receive the results of performed calculations.

Matrix multiplication

The problem of matrix-matrix multiplication is defined by the relations

.

(for simplicity of presentation, we will assume that the multiplied matrices and are square and have order ).

An analysis of possible methods for parallel execution of this task can be carried out by analogy with the consideration of the problem of multiplying a matrix by a vector. Leaving such an analysis for independent study, we will use the example of the matrix multiplication problem to show the use of several general approaches that allow us to form parallel methods for solving complex problems.

So, in the previous lesson we looked at the rules for adding and subtracting matrices. These are such simple operations that most students understand them literally right off the bat.

However, you rejoice early. The freebie is over - let's move on to multiplication. I’ll warn you right away: multiplying two matrices is not at all multiplying numbers located in cells with the same coordinates, as you might think. Everything is much more fun here. And we will have to start with preliminary definitions.

Matched matrices

One of the most important characteristics of a matrix is ​​its size. We've already talked about this a hundred times: the notation $A=\left[ m\times n \right]$ means that the matrix has exactly $m$ rows and $n$ columns. We have already discussed how not to confuse rows with columns. Something else is important now.

Definition. Matrices of the form $A=\left[ m\times n \right]$ and $B=\left[ n\times k \right]$, in which the number of columns in the first matrix coincides with the number of rows in the second, are called consistent.

Once again: the number of columns in the first matrix is ​​equal to the number of rows in the second! From here we get two conclusions at once:

1. The order of the matrices is important to us. For example, the matrices $A=\left[ 3\times 2 \right]$ and $B=\left[ 2\times 5 \right]$ are consistent (2 columns in the first matrix and 2 rows in the second), but vice versa — matrices $B=\left[ 2\times 5 \right]$ and $A=\left[ 3\times 2 \right]$ are no longer consistent (5 columns in the first matrix are not 3 rows in the second ).
2. Consistency can be easily checked by writing down all the dimensions one after another. Using the example from the previous paragraph: “3 2 2 5” - there are identical numbers in the middle, so the matrices are consistent. But “2 5 3 2” are not consistent, since there are different numbers in the middle.

In addition, Captain Obviousness seems to hint that square matrices of the same size $\left[ n\times n \right]$ are always consistent.

In mathematics, when the order of listing objects is important (for example, in the definition discussed above, the order of matrices is important), we often talk about ordered pairs. We met them back in school: I think it’s a no brainer that the coordinates $\left(1;0 \right)$ and $\left(0;1 \right)$ define different points on the plane.

So: coordinates are also ordered pairs that are made up of numbers. But nothing prevents you from making such a pair from matrices. Then we can say: “An ordered pair of matrices $\left(A;B \right)$ is consistent if the number of columns in the first matrix is ​​the same as the number of rows in the second.”

Well, so what?

Definition of multiplication

Consider two consistent matrices: $A=\left[ m\times n \right]$ and $B=\left[ n\times k \right]$. And we define the multiplication operation for them.

Definition. The product of two matched matrices $A=\left[ m\times n \right]$ and $B=\left[ n\times k \right]$ is the new matrix $C=\left[ m\times k \right] $, the elements of which are calculated using the formula:

\[\begin(align) & ((c)_(i;j))=((a)_(i;1))\cdot ((b)_(1;j))+((a)_ (i;2))\cdot ((b)_(2;j))+\ldots +((a)_(i;n))\cdot ((b)_(n;j))= \\ & =\sum\limits_(t=1)^(n)(((a)_(i;t))\cdot ((b)_(t;j))) \end(align)\]

Such a product is denoted in the standard way: $C=A\cdot B$.

Those who see this definition for the first time immediately have two questions:

1. What kind of fierce game is this?
2. Why is it so difficult?

Well, first things first. Let's start with the first question. What do all these indices mean? And how not to make mistakes when working with real matrices?

First of all, we note that the long line for calculating $((c)_(i;j))$ (I specially put a semicolon between the indices so as not to get confused, but there is no need to put them in general - I myself got tired of typing the formula in the definition) actually comes down to a simple rule:

1. Take the $i$th row in the first matrix;
2. Take the $j$th column in the second matrix;
3. We get two sequences of numbers. We multiply the elements of these sequences with the same numbers, and then add the resulting products.

This process is easy to understand from the picture:

Once again: we fix row $i$ in the first matrix, column $j$ in the second matrix, multiply elements with the same numbers, and then add the resulting products - we get $((c)_(ij))$. And so on for all $1\le i\le m$ and $1\le j\le k$. Those. There will be $m\times k$ of such “perversions” in total.

In fact, we have already encountered matrix multiplication in the school curriculum, only in a greatly reduced form. Let the vectors be given:

\[\begin(align) & \vec(a)=\left(((x)_(a));((y)_(a));((z)_(a)) \right); \\ & \overrightarrow(b)=\left(((x)_(b));((y)_(b));((z)_(b)) \right). \\ \end(align)\]

Then their scalar product will be exactly the sum of pairwise products:

\[\overrightarrow(a)\times \overrightarrow(b)=((x)_(a))\cdot ((x)_(b))+((y)_(a))\cdot ((y )_(b))+((z)_(a))\cdot ((z)_(b))\]

Basically, back when the trees were greener and the skies were brighter, we simply multiplied the row vector $\overrightarrow(a)$ by the column vector $\overrightarrow(b)$.

Nothing has changed today. It’s just that now there are more of these row and column vectors.

But enough theory! Let's look at real examples. And let's start with the simplest case - square matrices.

Square matrix multiplication

Task 1. Do the multiplication:

\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]\]

Solution. So, we have two matrices: $A=\left[ 2\times 2 \right]$ and $B=\left[ 2\times 2 \right]$. It is clear that they are consistent (square matrices of the same size are always consistent). Therefore, we perform the multiplication:

\[\begin(align) & \left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \ begin(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot \left(-2 \right)+2\cdot 3 & 1\cdot 4+2\cdot 1 \\ -3\cdot \left(-2 \right)+4\cdot 3 & -3\cdot 4+4\cdot 1 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 4 & 6 \\ 18 & -8 \\\ end(array)\right]. \end(align)\]

That's all!

Answer: $\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]$.

Task 2. Do the multiplication:

\[\left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)(r))9 & 6 \\ -3 & -2 \\\end(array) \right]\]

Solution. Again, consistent matrices, so we perform the following actions:\[\]

\[\begin(align) & \left[ \begin(matrix) 1 & 3 \\ 2 & 6 \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)() r)) 9 & 6 \\ -3 & -2 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 1\cdot 9+3\cdot \ left(-3 \right) & 1\cdot 6+3\cdot \left(-2 \right) \\ 2\cdot 9+6\cdot \left(-3 \right) & 2\cdot 6+6\ cdot \left(-2 \right) \\\end(array) \right]= \\ & =\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right] . \end(align)\]

As you can see, the result is a matrix filled with zeros

Answer: $\left[ \begin(matrix) 0 & 0 \\ 0 & 0 \\\end(matrix) \right]$.

From the examples given, it is obvious that matrix multiplication is not such a complicated operation. At least for 2 by 2 square matrices.

In the process of calculations, we compiled an intermediate matrix, where we directly described which numbers are included in a particular cell. This is exactly what should be done when solving real problems.

Basic properties of the matrix product

In a nutshell. Matrix multiplication:

1. Non-commutative: $A\cdot B\ne B\cdot A$ in the general case. There are, of course, special matrices for which the equality $A\cdot B=B\cdot A$ (for example, if $B=E$ is the identity matrix), but in the vast majority of cases this does not work;
2. Associatively: $\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)$. There are no options here: adjacent matrices can be multiplied without worrying about what is to the left and to the right of these two matrices.
3. Distributively: $A\cdot \left(B+C \right)=A\cdot B+A\cdot C$ and $\left(A+B \right)\cdot C=A\cdot C+B\cdot C $ (due to the non-commutativity of the product, it is necessary to separately specify right and left distributivity.

And now - everything is the same, but in more detail.

Matrix multiplication is in many ways similar to classical number multiplication. But there are differences, the most important of which is that Matrix multiplication is, generally speaking, non-commutative.

Let's look again at the matrices from Problem 1. We already know their direct product:

\[\left[ \begin(array)(*(35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]=\left[ \begin(array)(*(35)(r))4 & 6 \\ 18 & -8 \\\end(array) \right]\]

But if we swap the matrices, we get a completely different result:

\[\left[ \begin(array)(*(35)(r)) -2 & 4 \\ 3 & 1 \\\end(array) \right]\cdot \left[ \begin(array)(* (35)(r)) 1 & 2 \\ -3 & 4 \\\end(array) \right]=\left[ \begin(matrix) -14 & 4 \\ 0 & 10 \\\end(matrix )\right]\]

It turns out that $A\cdot B\ne B\cdot A$. In addition, the multiplication operation is only defined for the consistent matrices $A=\left[ m\times n \right]$ and $B=\left[ n\times k \right]$, but no one has guaranteed that they will remain consistent. if they are swapped. For example, the matrices $\left[ 2\times 3 \right]$ and $\left[ 3\times 5 \right]$ are quite consistent in the specified order, but the same matrices $\left[ 3\times 5 \right] $ and $\left[ 2\times 3 \right]$ written in reverse order are no longer consistent. Sad.:(

Among square matrices of a given size $n$ there will always be those that give the same result both when multiplied in direct and in reverse order. How to describe all such matrices (and how many there are in general) is a topic for a separate lesson. We won't talk about that today. :)

However, matrix multiplication is associative:

\[\left(A\cdot B \right)\cdot C=A\cdot \left(B\cdot C \right)\]

Therefore, when you need to multiply several matrices in a row at once, it is not at all necessary to do it straight away: it is quite possible that some adjacent matrices, when multiplied, give an interesting result. For example, a zero matrix, as in Problem 2 discussed above.

In real problems, most often we have to multiply square matrices of size $\left[ n\times n \right]$. The set of all such matrices is denoted by $((M)^(n))$ (i.e., the entries $A=\left[ n\times n \right]$ and \ mean the same thing), and it will necessarily contain matrix $E$, which is called the identity matrix.

Definition. An identity matrix of size $n$ is a matrix $E$ such that for any square matrix $A=\left[ n\times n \right]$ the equality holds:

Such a matrix always looks the same: there are ones on its main diagonal, and zeros in all other cells.

\[\begin(align) & A\cdot \left(B+C \right)=A\cdot B+A\cdot C; \\ & \left(A+B \right)\cdot C=A\cdot C+B\cdot C. \\ \end(align)\]

In other words, if you need to multiply one matrix by the sum of two others, then you can multiply it by each of these “two others”, and then add the results. In practice, we usually have to perform the opposite operation: we notice the same matrix, take it out of brackets, perform addition and thereby simplify our life. :)

Note: to describe distributivity, we had to write two formulas: where the sum is in the second factor and where the sum is in the first. This happens precisely because matrix multiplication is non-commutative (and in general, in non-commutative algebra there are a lot of fun things that don’t even come to mind when working with ordinary numbers). And if, for example, you need to write down this property in an exam, then be sure to write both formulas, otherwise the teacher may get a little angry.

Okay, these were all fairy tales about square matrices. What about rectangular ones?

The case of rectangular matrices

But nothing - everything is the same as with square ones.

Task 3. Do the multiplication:

\[\left[ \begin(matrix) \begin(matrix) 5 \\ 2 \\ 3 \\\end(matrix) & \begin(matrix) 4 \\ 5 \\ 1 \\\end(matrix) \ \\end(matrix) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]\]

Solution. We have two matrices: $A=\left[ 3\times 2 \right]$ and $B=\left[ 2\times 2 \right]$. Let's write down the numbers indicating the sizes in a row:

As you can see, the central two numbers coincide. This means that the matrices are consistent and can be multiplied. Moreover, at the output we get the matrix $C=\left[ 3\times 2 \right]$:

\[\begin(align) & \left[ \begin(matrix) \begin(matrix) 5 \\ 2 \\ 3 \\\end(matrix) & \begin(matrix) 4 \\ 5 \\ 1 \\ \end(matrix) \\\end(matrix) \right]\cdot \left[ \begin(array)(*(35)(r)) -2 & 5 \\ 3 & 4 \\\end(array) \right]=\left[ \begin(array)(*(35)(r)) 5\cdot \left(-2 \right)+4\cdot 3 & 5\cdot 5+4\cdot 4 \\ 2 \cdot \left(-2 \right)+5\cdot 3 & 2\cdot 5+5\cdot 4 \\ 3\cdot \left(-2 \right)+1\cdot 3 & 3\cdot 5+1 \cdot 4 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 2 & 41 \\ 11 & 30 \\ -3 & 19 \ \\end(array) \right]. \end(align)\]

Everything is clear: the final matrix has 3 rows and 2 columns. Quite $=\left[ 3\times 2 \right]$.

Answer: $\left[ \begin(array)(*(35)(r)) \begin(array)(*(35)(r)) 2 \\ 11 \\ -3 \\\end(array) & \begin(matrix) 41 \\ 30 \\ 19 \\\end(matrix) \\\end(array) \right]$.

Now let's look at one of the best training tasks for those who are just starting to work with matrices. In it you need not just multiply some two tablets, but first determine: is such multiplication permissible?

Problem 4. Find all possible pairwise products of matrices:

\\]; $B=\left[ \begin(matrix) \begin(matrix) 0 \\ 2 \\ 0 \\ 4 \\\end(matrix) & \begin(matrix) 1 \\ 0 \\ 3 \\ 0 \ \\end(matrix) \\\end(matrix) \right]$; $C=\left[ \begin(matrix)0 & 1 \\ 1 & 0 \\\end(matrix) \right]$.

Solution. First, let's write down the sizes of the matrices:

\;\ B=\left[ 4\times 2 \right];\ C=\left[ 2\times 2 \right]\]

We find that the matrix $A$ can only be reconciled with the matrix $B$, since the number of columns of $A$ is 4, and only $B$ has this number of rows. Therefore, we can find the product:

\\cdot \left[ \begin(array)(*(35)(r)) 0 & 1 \\ 2 & 0 \\ 0 & 3 \\ 4 & 0 \\\end(array) \right]=\ left[ \begin(array)(*(35)(r))-10 & 7 \\ 10 & 7 \\\end(array) \right]\]

I suggest the reader complete the intermediate steps independently. I will only note that it is better to determine the size of the resulting matrix in advance, even before any calculations:

\\cdot \left[ 4\times 2 \right]=\left[ 2\times 2 \right]\]

In other words, we simply remove the “transit” coefficients that ensured the consistency of the matrices.

What other options are possible? Of course, one can find $B\cdot A$, since $B=\left[ 4\times 2 \right]$, $A=\left[ 2\times 4 \right]$, so the ordered pair $\left(B ;A \right)$ is consistent, and the dimension of the product will be:

\\cdot \left[ 2\times 4 \right]=\left[ 4\times 4 \right]\]

In short, the output will be a matrix $\left[ 4\times 4 \right]$, the coefficients of which can be easily calculated:

\\cdot \left[ \begin(array)(*(35)(r)) 1 & -1 & 2 & -2 \\ 1 & 1 & 2 & 2 \\\end(array) \right]=\ left[ \begin(array)(*(35)(r))1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(array) \right]\]

Obviously, you can also agree on $C\cdot A$ and $B\cdot C$ - and that’s it. Therefore, we simply write down the resulting products:

It was easy.:)

Answer: $AB=\left[ \begin(array)(*(35)(r)) -10 & 7 \\ 10 & 7 \\\end(array) \right]$; $BA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 2 & -2 & 4 & -4 \\ 3 & 3 & 6 & 6 \\ 4 & -4 & 8 & -8 \\\end(array) \right]$; $CA=\left[ \begin(array)(*(35)(r)) 1 & 1 & 2 & 2 \\ 1 & -1 & 2 & -2 \\\end(array) \right]$; $BC=\left[ \begin(array)(*(35)(r))1 & 0 \\ 0 & 2 \\ 3 & 0 \\ 0 & 4 \\\end(array) \right]$.

In general, I highly recommend doing this task yourself. And one more similar task that is in homework. These seemingly simple thoughts will help you practice all the key stages of matrix multiplication.

But the story doesn't end there. Let's move on to special cases of multiplication. :)

Row vectors and column vectors

One of the most common matrix operations is multiplication by a matrix that has one row or one column.

Definition. A column vector is a matrix of size $\left[ m\times 1 \right]$, i.e. consisting of several rows and only one column.

A row vector is a matrix of size $\left[ 1\times n \right]$, i.e. consisting of one row and several columns.

In fact, we have already encountered these objects. For example, an ordinary three-dimensional vector from stereometry $\overrightarrow(a)=\left(x;y;z \right)$ is nothing more than a row vector. From a theoretical point of view, there is almost no difference between rows and columns. You only need to be careful when coordinating with the surrounding multiplier matrices.

Task 5. Do the multiplication:

\[\left[ \begin(array)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(array) \right] \cdot \left[ \begin(array)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(array) \right]\]

Solution. Here we have the product of matched matrices: $\left[ 3\times 3 \right]\cdot \left[ 3\times 1 \right]=\left[ 3\times 1 \right]$. Let's find this piece:

\[\left[ \begin(array)(*(35)(r)) 2 & -1 & 3 \\ 4 & 2 & 0 \\ -1 & 1 & 1 \\\end(array) \right] \cdot \left[ \begin(array)(*(35)(r)) 1 \\ 2 \\ -1 \\\end(array) \right]=\left[ \begin(array)(*(35 )(r)) 2\cdot 1+\left(-1 \right)\cdot 2+3\cdot \left(-1 \right) \\ 4\cdot 1+2\cdot 2+0\cdot 2 \ \ -1\cdot 1+1\cdot 2+1\cdot \left(-1 \right) \\\end(array) \right]=\left[ \begin(array)(*(35)(r) ) -3 \\ 8 \\ 0 \\\end(array) \right]\]

Answer: $\left[ \begin(array)(*(35)(r))-3 \\ 8 \\ 0 \\\end(array) \right]$.

Task 6. Do the multiplication:

\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(array) \right]\]

Solution. Again everything is agreed: $\left[ 1\times 3 \right]\cdot \left[ 3\times 3 \right]=\left[ 1\times 3 \right]$. We count the product:

\[\left[ \begin(array)(*(35)(r)) 1 & 2 & -3 \\\end(array) \right]\cdot \left[ \begin(array)(*(35) (r)) 3 & 1 & -1 \\ 4 & -1 & 3 \\ 2 & 6 & 0 \\\end(array) \right]=\left[ \begin(array)(*(35)() r))5 & -19 & 5 \\\end(array) \right]\]

Answer: $\left[ \begin(matrix) 5 & -19 & 5 \\\end(matrix) \right]$.

As you can see, when we multiply a row vector and a column vector by a square matrix, the output always results in a row or column of the same size. This fact has many applications - from solving linear equations to all kinds of coordinate transformations (which ultimately also come down to systems of equations, but let's not talk about sad things).

I think everything was obvious here. Let's move on to the final part of today's lesson.

Matrix exponentiation

Among all the multiplication operations, exponentiation deserves special attention - this is when we multiply the same object by itself several times. Matrices are no exception; they can also be raised to various powers.

Such works are always agreed upon:

\\cdot \left[ n\times n \right]=\left[ n\times n \right]\]

And they are designated in exactly the same way as ordinary degrees:

\[\begin(align) & A\cdot A=((A)^(2)); \\ & A\cdot A\cdot A=((A)^(3)); \\ & \underbrace(A\cdot A\cdot \ldots \cdot A)_(n)=((A)^(n)). \\ \end(align)\]

At first glance, everything is simple. Let's see what this looks like in practice:

Task 7. Raise the matrix to the indicated power:

$((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))$

Solution. Well OK, let's build. First let's square it:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(2))=\left[ \begin(matrix ) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1\cdot 1+1\cdot 0 & 1\cdot 1+1\cdot 1 \\ 0\cdot 1+1\cdot 0 & 0\cdot 1+1\cdot 1 \\\end(array) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \ \\end(array) \right] \end(align)\]

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))=((\left[ \begin (matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end( matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 2 \\ 0 & 1 \\\end(array) \right]\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r)) 1 & 3 \\ 0 & 1 \\\end(array) \right] \end(align)\]

That's all.:)

Answer: $\left[ \begin(matrix)1 & 3 \\ 0 & 1 \\\end(matrix) \right]$.

Problem 8. Raise the matrix to the indicated power:

\[((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))\]

Solution. Just don’t cry now about the fact that “the degree is too big,” “the world is not fair,” and “the teachers have completely lost their shores.” It's actually easy:

\[\begin(align) & ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(10))=((\left[ \begin (matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))\cdot ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\ end(matrix) \right])^(3))\cdot ((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(3))\ cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left(\left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrix) \right] \right)\cdot \left(\left[ \begin(matrix) 1 & 3 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right ] \right)= \\ & =\left[ \begin(matrix) 1 & 6 \\ 0 & 1 \\\end(matrix) \right]\cdot \left[ \begin(matrix) 1 & 4 \\ 0 & 1 \\\end(matrix) \right]= \\ & =\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right] \end(align)\ ]

Notice that in the second line we used multiplication associativity. Actually, we used it in the previous task, but it was implicit there.

Answer: $\left[ \begin(matrix) 1 & 10 \\ 0 & 1 \\\end(matrix) \right]$.

As you can see, there is nothing complicated about raising a matrix to a power. The last example can be summarized:

\[((\left[ \begin(matrix) 1 & 1 \\ 0 & 1 \\\end(matrix) \right])^(n))=\left[ \begin(array)(*(35) (r)) 1 & n \\ 0 & 1 \\\end(array) \right]\]

This fact is easy to prove through mathematical induction or direct multiplication. However, it is not always possible to catch such patterns when raising to a power. Therefore, be careful: often multiplying several matrices “at random” turns out to be easier and faster than looking for some kind of patterns.

In general, do not look for higher meaning where there is none. In conclusion, let's consider exponentiation of a larger matrix - as much as $\left[ 3\times 3 \right]$.

Problem 9. Raise the matrix to the indicated power:

\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))\]

Solution. Let's not look for patterns. We work ahead:

\[((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(3))=(( \left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^(2))\cdot \left[ \begin (matrix)0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right]\]

First, let's square this matrix:

\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 2))=\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right]\cdot \left[ \begin(matrix ) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right]= \\ & =\left[ \begin(array)(*(35)(r )) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \end(align)\]

Now let's cube it:

\[\begin(align) & ((\left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right])^( 3))=\left[ \begin(array)(*(35)(r)) 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \\\end(array) \right] \cdot \left[ \begin(matrix) 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\\end(matrix) \right]= \\ & =\left[ \begin( array)(*(35)(r)) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(array) \right] \end(align)\]

That's all. The problem is solved.

Answer: $\left[ \begin(matrix) 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \\\end(matrix) \right]$.

As you can see, the volume of calculations has become larger, but the meaning has not changed at all. :)

This concludes the lesson. Next time we will consider the inverse operation: using the existing product we will look for the original factors.

As you probably already guessed, we will talk about the inverse matrix and methods for finding it.