Square Matrix

If for a two-dimensional array, at a certain run of the program, we also use for the number of lines and for the number of columns the same value, it is called quadratic (square matrix). In this material we will study various peculiarities that appear in such matrix. Basically, everything we discussed at the presentation generality of matrices is valid, but here some new things appear. In the table below, for an square matrix of size 7 (7 lines and 7 columns) with the lines and columns indexed from 1, I noted only the indices the elements.

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

The discussion revolves around the fact that, as I also pointed out in the figure, if it leaves from one corner and advance diagonally, it reaches the exact opposite corner (obviously this is valid just because the matrix is ​​square).

What is hatched above is called the main diagonal. If it starts from the right corner of the top line (1,7) and moving forward diagonally, you will reach the lower left corner (7,1). The area covered in this way is called the secondary diagonal.

The main diagonal and the areas bounded by it


We will take care of visiting the elements of certain formed areas. With the crossed elements we can achieve various classic operations (sums, products, counts, maximums, minimums, checks, etc.) but in the examples next we will realize, for simplicity, the sum

Sum of the elements on the main diagonal


We notice that the elements on the main diagonal have equal row and column indices. They are the only ones matrix elements with equal indices. So a first solution is to traverse the entire array and, with an if, we only select elements with this property.

for (i = 1;i <= n; i++)
    for (j = 1;j <= n; j++)
        if (i == j)
          sum += a[i][j];

We notice that for both lines and columns we go with indices up to n (we considered a matrix quadratic of dimension n, as we will also consider in the following examples).

Here is another way to sum the elements on the main diagonal:

for (i = 1;i <= n; i++)
    sum += a[i][i];

The above code is also correct, it is shorter and it is more efficient (we have time of order n to unlike the first variant where the execution time is of order n2 ). How did I think to get to it?

We imagined the for counter as the line we want to visit, and we notice that on the current line there is only one element we are interested in and that the column index has the same value as the row index, fixed through the for

A generally valid idea is the following: if the area to be crossed is linear (a particular line of the matrix, o specific column of the matrix, a specific diagonal, etc.) then the visit can be done with only one structure repetitive; if the area to be crossed is like a surface (the matrix itself or a certain part of it arranged on several lines and several columns), then visiting its elements must be done with two forums, one with which indicates the line we are on and the other for visiting the elements on the fixed line.

We will see more of the above in the following sections

Traversing the elements in the triangle bounded by the main diagonal, located below it

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

Analyzing the index table we notice that the elements located in the area we are interested in have the property that the row index is greater than the column index and only in this area the elements have this property. Thus, we can traverse the entire array and, with an if, select these elements.

for (i = 1; i <= n; i++)
    for (j = 1;j <= n; j++)
        if (i > j)
            sum += a[i][j];

The code shown visits the elements in the area strictly below the diagonal. To include the diagonal was just change the comparison sign of the if condition from > to >=.

A better option than the one presented is to carefully consider how we can visit only elements in the area which interests us. We would thus halve the execution time (in the area we are interested in are about half of the matrix elements)

We notice that the lines covered by the area elements are between 2 and n.

  • On line 2, the columns are 1 to 1
  • On line 3, the columns are 1 to 2
  • On line 4, columns are 1 to 3
  • ...
  • On row n the columns are from 1 to n-1.
    •

So, if we visit with the first for the lines (i being the index, so the current line), the column (so the index j from second for) will be between 1 and i-1.

for (i = 1;i <= n; i++)
    for (j = 1; j < i; j++)
        sum += a[i][j];

This variant has the theoretical time complexity of order n2 , like the first one, but the actual number of operations is lower (about half).

Traversing the elements in the triangle bounded by the main diagonal, located above it.

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

We will present, as above, two approaches:

  • We observe the relationship between the indices for the elements of the area and select them with if during the loop the entire matrix;
  • We fix with an index the lines with elements that interest us and vary the column on the line with another index current after observing the general rule that we apply to each line;

Option 1.

The elements of the desired area are those with the row index strictly less than the column index.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n; j++)
        if (i < j)
            sum += a[i][j];

Options 2.

We notice that we are interested in lines from 1 to n-1

  • On line 1 we have columns from 2 to n
  • On line 2 we have columns from 3 to n
  • On line 3 we have columns from 4 to n
  • ...
  • On line n-1 we have columns from n to n
    •  
for (i = 1;i <= n; i++)
    for (j = i+1;j <= n; j++)
        sum += a[i][j];

In relation to the main diagonal and the other diagonals "parallel" to it, we make the following observations:

  • I said that for the elements on the main diagonal i=j. This is equivalent to i-j=0.
  • The elements on the parallel to the main diagonal immediately below it have i-j=1.
  • The diagonal elements below the previous one have i-j=2.
  • On the other side, the elements of the diagonal immediately above the main one have i-j=-1.

In conclusion, the elements on the main diagonal or on the same parallel to it have the difference of indices constant.

The secondary diagonal and the areas bounded by it

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

This time we will start somehow in reverse with the observations, namely: for the elements on the diagonal secondary the sum of the indices is n+1. Looking carefully we see that on each parallel to the secondary diagonal the sum of the indices is constant. So on the parallel located immediately above the sum of the indices is n, on the one still located one level higher, the sum of the indices is n-1, etc

So, on the parallels to the main diagonal we have a constant index difference and on the parallels to the diagonal secondary we have a constant index sum.

Going through the elements on the secondary diagonal

Variant 1. It is the non-optimal one: we go through the entire matrix and put the condition i+j=n+1

for (i = 1;i <= n; i++)
    for (j = 1;j <= n;j++)
        if (i + j == n + 1)
            sum += a[i][j];

Variant 2. We notice that the travel area is linear, so we must be able to solve it with a square. We fix the index of this as the line where we have elements (from 1 to n here) and we calculate the column as n + 1 - currentline

for (i = 1;i <= n; i++)
    sum += a[i][n + 1 - i]; /// or a[i][n - i + 1]

Traversing the elements in the triangle bounded by the secondary diagonal, located below it

The first variant is based on the observation that the elements of this area are those for which i+j>n+1. Therefore we can loop through the entire array and select with if only these elements.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n; j++)
        if (i + j > n + 1)
            sum += a[i][j];

The second variant, the one in which we visit exactly the elements of the area, is based on the observation:

  • We have elements on lines from 2 to n;
  • At a certain line i, the elements we are interested in are the ones after the one on the diagonal secondary from line i and to the end of the line. So the indices are from (n+1-i)+1 to n. I have written for didactic purposes, the formula but in the code we write compact n-i+2.
for (i = 2;i <= n; i++)
    for (j = n - i + 2; j <= n; j++)
        sum += a[i][j];

Traversing the elements in the triangle bounded by the secondary diagonal, located above it

Option 1: the elements we are interested in are those with the sum of indices less than n+1.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n;j++)
        if (i + j < n + 1)
            sum += a[i][j];

Option 2: we make the observations

  • We have elements on lines from 1 to n-1;
  • At a certain line i, the elements we are interested in are those at the beginning of the line, so the column 1, until before the one on the secondary diagonal, that is, we go with the column up to n-i
for (i = 1; i < n; i++)
    for (j = 1; j <= n-i; j++)
        sum += a[i][j];

Solved Problems:

The ideas used to solve these problems are classic ones, often found in practice.

1. A number n is read from the keyboard. Construct a square matrix of size n, after the following rules:

  • The elements on the main diagonal should have the value 1;
  • The elements in the triangle below the main diagonal should have the value 2;
  • The elements in the triangle above the main diagonal should have the value 3.

Example:

Input Output
5 
1 3 3 3 3
2 1 3 3 3
2 2 1 3 3
2 2 2 1 3
2 2 2 2 1

Solution:

We notice that this time not all the values ​​of a matrix are read from the keyboard. We have to build one starting from its size. Since we have to visit all the elements, it is necessary to use the method that traverses the entire array and which, with if, identifies the area we are in. Further we present only the code sequence assuming that the matrix to be constructed is called a.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n;j++) {
        if (i == j)
            a[i][j] = 1;
        else
            if (i > j)
                a[i][j] = 2;
            else
                a[i][j] = 3;
}

I have only shown the sequence of storing values ​​in the array without displaying the array afterwards.

2. A number n is read from the keyboard. Construct a square matrix of size n after the rules:

  • The elements of the two diagonals have the value 1;
  • The elements of the upper triangle bounded by the two diagonals have the value 2;
  • The elements of the bottom triangle bounded by the two diagonals have the value 3;
  • The elements of the triangle on the left bounded by the two diagonals have the value 4;
  • The elements of the triangle on the right bounded by the two diagonals have the value 5;

Example:

Input Output
5 
1 2 2 2 1
4 1 2 1 5
4 4 1 5 5
4 1 3 1 5
1 3 3 3 1

Solution:

We apply the same technique from the previous problem, traversing the entire matrix and identifying the area where we we find out. For triangular areas bounded by two diagonals we use if with two conditions, one condition each to indicate which side the current element is on each diagonal.

for (i = 1;i <= n; i++)
    for (j = 1;j <= n; j++) {
        if (i == j || i + j == n + 1)
            a[i][j] = 1;
        if (i < j || i + j < n + 1)
            a[i][j] = 2;
        if (i > j || i + j > n + 1)
            a[i][j] = 3;
        if (i > j || i + j < n + 1)
            a[i][j] = 4;
        if (i < j || i + j > n + 1)
            a[i][j] = 4;
}

For this problem I chose the variant with successive ifs instead of the one with if-else-if since the code is more compact.