Examples of Matrix Processing Algorithms

Matrix processing algorithms

A matrix is a two-dimensional array, each element of which has two indices: row number – i ; column number – j . Therefore, to work with matrix elements, two loops must be used. If the values of the parameter of the first cycle will be the numbers of the rows of the matrix, then the values of the parameter of the second will be the columns (or vice versa). The processing of the matrix consists in the fact that at first the elements of the first row (column) are considered in turn, then the second, and so on. to the last. Consider the basic operations performed on matrices when solving problems.

Matrix input-output algorithm

Matrices, like arrays, must be entered (output) element by element. The block diagram of input of matrix elements is shown in fig. 4.1. The output of the matrix is organized similarly to the input.

Rice. 4.1. Entering Matrix Elements Rice. 4.2. Matrix element properties

Let’s consider several problems of processing matrices. To solve them, let us remind the reader of some properties of matrices (Fig. 4.2):

  • if the row number of the element matches the column number (i = j) , this means that the element lies on the main diagonal of the matrix;
  • if the row number exceeds the column number (i > j) , then the element is below the main diagonal;
  • if the column number is greater than the row number (i , then the element is above the main diagonal.
  • an element lies on the secondary diagonal if its indices satisfy the equality i+j-1 = n ;
  • the inequality i+j-1 < n is typical for the element located above the secondary diagonal;
  • accordingly, the element lying below the secondary diagonal corresponds to the expression i+j-1 > n .

Examples of Matrix Processing Algorithms

EXAMPLE 4.1. Find the sum of the matrix elements lying above the main diagonal (Figure 4.3).

Rice. 4.3. Figure for the condition of the problem from example 4.1

The algorithm for solving this problem (Fig. 4.4) is constructed as follows: the cell for accumulating the sum is set to zero (variable S ). Then, using two loops (the first in rows, the second in columns), each element of the matrix is scanned, but the summation occurs only if this element is above the main diagonal, that is, the i < j property is satisfied.

Figure 4.5 shows another solution to this problem. It does not check the condition i , but, nevertheless, it also sums up the matrix elements that are above the main diagonal. To understand how this algorithm works, let’s go back to Figure 4.3. In the first row of the given matrix, it is necessary to add all the elements, starting from the second. In the second – everything starting from the third, in the i -th line the process will start from the (i + 1) -th element, and so on. So the first loop runs from 1 to N , and the second from i+1 to M . We invite the reader to independently create a program corresponding to the described algorithm.

Rice. 4.4. Flowchart of Example 4.1 (Algorithm 1) Rice. 4.5. Flowchart of Example 4.1 (Algorithm 2)

EXAMPLE 4.2. Calculate the number of positive elements of a square matrix located along its perimeter and on the diagonals. Recall that in a square matrix, the number of rows is equal to the number of columns.

Before proceeding to solve the problem, consider Figure 4.6, which shows a diagram of square matrices of various dimensions. It is clear from the condition of the problem that it is not necessary to consider all elements of a given matrix. It is enough to view the first and last rows, the first and last columns, as well as the diagonals. All these elements are marked on the diagram, and elements that can be accessed twice are highlighted in black. For example, the element with number (1,1) belongs to both the first row and the first column, and the element with number (N,N) is in the last row and the last column at the same time. In addition, if N is an odd number (in Figure 4.6 this matrix is located on the left), then there is an element with the number (N/2+1, N/2+1) that is located at the intersection of the main and secondary diagonals. For an odd value of N (the matrix on the right in Fig. 4.6), the diagonals do not intersect.

Rice. 4.6. Figure for the condition of the problem from example 4.2

So, having analyzed in detail the formulation of the problem, we consider the algorithm for solving it. To refer to the elements of the main diagonal, remember that the row numbers of these elements are always equal to the column numbers. Therefore, if the parameter i changes cyclically from 1 to N , then Ai,i is an element of the main diagonal. Using the property characteristic of the elements of the side diagonal, we get: i + j-1 u003d n > j = n-i + 1 , therefore, for i u003d 1,2, …, n , the element Аi, n-i + 1 is an element of the side diagonal . The elements located along the perimeter of the matrix are written as follows: A1,i – the first row, AN,i – the last row and, accordingly , Ai,1 – the first column, Ai,N – the last column.

The block diagram of the described algorithm is shown in fig. 4.7. In block 1, a loop is organized to access the diagonal elements of the matrix. Moreover, in blocks 2-3, the number of positive elements on the main diagonal is counted, and in blocks 5-6 on the side. The loop in block 6 specifies the change of parameter i from 2 to N-1 . This is necessary in order not to refer to elements that have already been considered: A 11 , A 1N , A N,1 and A N,N . Blocks 7-8 count positive elements in the first row, 9 and 10 in the last row, 11 and 12 in the first column, and 13 and 14 in the last. Block 15 checks if the element located at the intersection of the diagonals has been counted twice. Recall that this could only happen if N is an odd number and this element was positive. These conditions are checked in block 16, which reduces the calculated number of positive elements by one.

Rice. 4.7. Flowchart for Example 4.2

EXAMPLE 4.3. Check if the given square matrix is identity. An identity matrix is a matrix in which the elements of the main diagonal are ones, and all the rest are zeros.

Let’s solve the problem like this. Assume that the matrix is identity (FL=TRUE) and try to prove the opposite. If it turns out that at least one diagonal element is not equal to one or any of the elements outside the diagonal is not equal to zero, then the matrix is not identity (FL=FALSE) . Using logical operations, all these conditions can be combined into one and make a block diagram (Fig. 4.8).

Rice. 4.8. Flowchart for Example 4.3

EXAMPLE 4.4. Transform the original matrix so that the first element of each row is replaced by the arithmetic mean of the elements in that row.

To solve this problem, you need to find in each line the sum of the elements, which is divided by their number. The result is written in the first element of the corresponding line. The block diagram of the solution algorithm is shown in fig. 4.9.

EXAMPLE 4.5. The matrix An, m is given . Form a vector P m , in which to write the row numbers of the maximum elements of each column.

The algorithm for solving this problem is as follows: for each column of the matrix, we find the maximum element and its number, the number of the maximum element of the j -th column of the matrix is written in the j -th element of the array P . The block diagram of the algorithm is shown in fig. 4.10.

Rice. 4.9. Example 4.4 Flowchart Rice. 4.10. Example 4.5 Flowchart

EXAMPLE 4.6. Write a program to multiply two matrices An,m and Bm,l .

For example, you need to multiply two matrices

Using the row-by-column rule, we get a matrix:

In general, the formula for finding the element Ci,j of the matrix has the form:

where i = 1,N and j = 1,L.

Please note that the multiplication operation can only be carried out if the number of rows of the left matrix matches the number of columns of the right one. Also, A >< B ≠ B >< A.

The block diagram shown in fig. 4.11, implements the calculation of each element of the matrix C as a sum according to the above formula.

EXAMPLE 4.7. Swap the n th and l th columns of the matrix A(k,m) . The block diagram is shown in fig. 4.12.

Rice. 4.11. Algorithm for multiplying two matrices Rice. 4.12. Flowchart of Example 4.7

EXAMPLE 4.8. Transform matrix A(m,n) so that each column is sorted in descending order. The algorithm for solving this problem boils down to the fact that the algorithm for ordering elements in an array already known to us from the previous chapter is performed for each column of the matrix. The block diagram is shown in fig. 4.13.

EXAMPLE 4.9. Transform matrix A(m,n) so that rows with odd indices are sorted in descending order, with even ones – in ascending order. The block diagram is shown in fig. 4.14.

Figure 4.13. Example 4.8 Flowchart Rice. 4.14. Example 4.9 Flowchart

Be First to Comment

Leave a Reply

Your email address will not be published.