# Matrices

## Special Matrices

They are square matrices($n\text{ x }n$ dimension) and they have more zeros and therefore we can store them separately to reduce space and time complexity. Some special matrices are:

1. Diagonal Matrix
2. Lower Triangular Matrix
3. Upper Triangular Matrix
4. Symmetric Matrix
5. Tridiagonal Matrix
6. Toeplitz Matrix
7. Band Matrix
8. Sparse Matrix

### 1. Diagonal Matrix

#### Definition:

It is a special matrix where all the elements except the diagonal are zero. The diagonal can have any value.

$$
\begin{align}
& M =
\left[
\begin{matrix}
3 & 0 & 0 & 0 & 0 \\
0 & 7 & 0 & 0 & 0 \\
0 & 0 & 4 & 0 & 0 \\
0 & 0 & 0 & 9 & 0 \\
0 & 0 & 0 & 0 & 6 \\
\end{matrix}
\right]\\
\\
& M[i,j] = 0 & 7\text{ if i $\neq$ j}
\end{align}
$$

#### Representation in Memory

##### i. As 2-D array:

$$
M =
\begin{array}
{|c|c|c|c|c|}
\hline 3 & 0 & 0 & 0 & 0 \\
\hline 0 & 7 & 0 & 0 & 0 \\
\hline 0 & 0 & 4 & 0 & 0 \\
\hline 0 & 0 & 0 & 9 & 0 \\
\hline 0 & 0 & 0 & 0 & 6 \\
\hline
\end{array}
$$

We don't usually use 2-D arrays to represent diagonal matrices because memory and time is wasted on processing the zero elements. Here the array takes 100 bytes(5 x 5 x 4(int size)) of memory.

##### ii. As 1-D array:

$$
A =
\begin{array}
{|c|c|c|c|c|}
\hline 3 & 7 & 4 & 9 & 6 \\
\hline
\end{array}
$$

Here, we only store the non-zero elements in the array,saving memory and processing time. Here only 20 bytes(5 x 4) of memory is used.

#### Operations

##### Setting an element

void Set(int A[], int i, int j, int data)
{
    if (i == j)
    {
        A[i-1] = data;
    }
}

##### Getting an element

int Get(int A[], int i, int j)
{
    if (i == j) return A[i-1];
    else return 0;
}

##### Display/Print

void Display(int A[])
{
    for (int i = 0; i < Length; i++)
    {
        for(int j = 0; j < Length; j++)
        {
            if (i == j) printf("%d ", A[i-1]);
            else printf("0");
        }
    }
    printf("\n");
}

### 2. Lower Triangular Matrix

#### Definition:

It is a square matrix in which the lower triangular part of the matrix are non-zero elements and the upper triangular part are all zeros.

$$
M =
\left[
\begin{matrix}
a_{11} & 0 & 0 & 0 & 0 \\
a_{21} & a_{22} & 0 & 0 & 0 \\
a_{31} & a_{32} & a_{33} & 0 & 0 \\
a_{41} & a_{42} & a_{43} & a_{44} & 0 \\
a_{51} & a_{52} & a_{53} & a_{54} & a_{55} \\
\end{matrix}
\right]
$$

$$
\begin{align}
M[i,j] & = 0 & \text{if i < j} \\
M[i,j] & = non-zero & \text{if i }\geq\text{j} \\
\\
\text{no. of non-zero elements} & = \frac{n(n+1)}{2} \\
\text{no. of zero elements} & = \frac{n(n-1)}{2}
\end{align}
$$

#### Representation

##### i. Row-major

$$
A =
\begin{array}
{|c|c|}
\hline a_{11} & a_{21} & a_{22} & a_{31} & a_{32} & a_{33} & a_{41} & a_{42} & a_{43} & a_{44} & a_{51} & a_{52} & a_{53} & a_{54} & a_{55}\\
\hline
\end{array}
$$

$$
Index(A[i][j]) = \left[\frac{i(i-1)}{2}\right] + j -1
$$

##### ii. Column-major

$$
A =
\begin{array}
{|c|c|}
\hline a_{11} & a_{21} & a_{31} & a_{41} & a_{51} & a_{22} & a_{32} & a_{42} & a_{52} & a_{33} & a_{43} & a_{53} & a_{44} & a_{54} & a_{55}\\
\hline
\end{array}
$$

$$
Index(A[i][j]) = \left[n(j-1) - \frac{(j-1)(j-2)}{2}\right] + i-j
$$

### Upper Triangular Matrix

#### Definition:

$$
M =
\left[
\begin{matrix}
a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\
0 & a_{22} & a_{23} & a_{24} & a_{25} \\
0 & 0 & a_{33} & a_{34} & a_{35} \\
0 & 0 & 0 & a_{44} & a_{45} \\
0 & 0 & 0 & 0 & a_{55} \\
\end{matrix}
\right]
$$

$$
\begin{align}
M[i,j] & = 0 & \text{if i > j} \\
M[i,j] & = non-zero & \text{if i }\leq\text{j} \\
\\
\end{align}
$$

#### Representation

##### i. Row-major

$$
A =
\begin{array}
{|c|c|}
\hline a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{22} & a_{23} & a_{24} & a_{25} & a_{33} & a_{34} & a_{35} & a_{44} & a_{45} & a_{55}\\
\hline
\end{array}
$$

$$
Index(A[i][j]) = \left[n(i-1) - \frac{(i-1)(i-2)}{2}\right] + j-i
$$

##### ii. Column-major

$$
A =
\begin{array}
{|c|c|}
\hline a_{11} & a_{12} & a_{22} & a_{13} & a_{23} & a_{33} & a_{14} & a_{24} & a_{34} & a_{44} & a_{15} & a_{25} & a_{35} & a_{45} & a_{55}\\
\hline
\end{array}
$$

$$
Index(A[i][j]) = \left[\frac{j(j-1)}{2}\right] + i-1
$$

### Symmetric Matrix

#### Definition:

$$
M =
\left[
\begin{matrix}
2 & 2 & 2 & 2 & 2 \\
2 & 3 & 3 & 3 & 3 \\
2 & 3 & 4 & 4 & 4 \\
2 & 3 & 4 & 5 & 5 \\
2 & 3 & 4 & 5 & 6 \\
\end{matrix}
\right]
$$

$$
M[i,j] = M[j,i]
$$

It can be stored as an upper or lower triangular matrix.

### TriDiagonal Matrix

#### Definition:

$$
M =
\left[
\begin{matrix}
a_{11} & a_{12} & 0 & 0 & 0 \\
a_{21} & a_{22} & a_{23} & 0 & 0 \\
0 & a_{32} & a_{33} & a_{34} & 0 \\
0 & 0 & a_{43} & a_{44} & a_{45} \\
0 & 0 & 0 & a_{54} & a_{55} \\
\end{matrix}
\right]
$$

$$
\begin{align}
M[i,j] & = non-zero & \text{if }|i-j| \leq 1 \\
M[i,j] & = 0 & \text{if }|i-j| > 1 \\
\text{No. of elements} & = n + n - 1 + n - 1\\
& = 3n-2
\\
\end{align}
$$

#### Representation

$$
A =
\begin{array}
{|c|c|}
\hline a_{21} & a_{32} & a_{43} & a_{54} & a_{11} & a_{22} & a_{33} & a_{44} & a_{55} & a_{12} & a_{23} & a_{34} & a_{45} \\
\hline
\end{array}
$$

$$
Index(A[i][j]) =
\begin{cases}
i-1 & \text{if } i-j=1 \\[2ex]
n-1+i-1 & \text{if } i-j=0 \\[2ex]
2n-1+i-1 & \text{if } i-j=-1 \\[2ex]
\end{cases}
$$

### Toeplitz Matrix

#### Definition:

$$
M =
\left[
\begin{matrix}
2 & 3 & 4 & 5 & 6 \\
7 & 2 & 3 & 4 & 5 \\
8 & 7 & 2 & 3 & 4 \\
9 & 8 & 7 & 2 & 3 \\
10 & 9 & 8 & 7 & 2 \\
\end{matrix}
\right]
$$

$$
\begin{aligned}
M[i,j] & = M[j-1,i-1] \\
\text{No. of elements} & = n+n-1 \\
& = 2n-1
\end{aligned}
$$

#### Representation

$$
A =
\begin{array}
{|c|c|}
\hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\end{array}
$$

$$
Index(A[i][j]) =
\begin{cases}
j-i & \text{if } i\leq j \\[2ex]
n+i-j-1 & \text{if } i>j
\end{cases}
$$

### Sparse Matrix

$$
M =
\left[
\begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 \\
0 & 0 & 8 & 0 & 0 & 10 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 & 0 \\
0 & 9 & 0 & 0 & 5 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{matrix}
\right]
$$

#### Representation

##### i. 3-column representation

First row is used to store metadata i.e, information about matrices. It contains no. of rows,columns, and non-zero elements.

| Row | Column | Element |
| --- | ------ | ------- |
| 9 | 9 | 8 |
| 1 | 8 | 3 |
| 2 | 3 | 8 |
| 2 | 6 | 10 |
| 4 | 1 | 4 |
| 6 | 3 | 2 |
| 7 | 4 | 6 |
| 8 | 2 | 9 |
| 8 | 5 | 5 |

##### ii. Compressed sparse rows

$$
\begin{aligned}
A &[3,8,10,4,2,6,9,5] \\
\text{IA} &[0,1,3,3,4,4,5,6,8] \\
\text{JA} &[8,3,6,1,3,4,2,5]\\
\end{aligned}
$$

- First rows store non-zero elements.
- Second row stores the no. of elements until the i^th
index. eg: 4 elements found TILL index 5.
- Third row stores the column number in which the element is present.

struct Element
{
    int i, j, data;
};

struct Sparse
{
    int m, n, num;
    struct Element* ele;
}

struct Sparse* Add(Sparse* s1, Sparse* s2)
{
    if (s1->m != s2->m || s1->n != s2->n)
    {
        return 0;
    }
    int i = 0, j = 0, k = 0;
    Sparse* sum = new Sparse();
    sum->m = s1->m;
    sum->n = s1->n;
    sum->ele = new Elements1->num + s2->num);

    while (i < s1->num && j < s2->num)
    {
        if (s1->ele[i].i < s2->ele[j].i)
        {
            sum->ele[k++] = s1->ele[i++];
        }
        else if (s1->ele[i].i > s2->ele[j].i)
        {
            sum->ele[k++] = s2->ele[i++];
        }
        else
        {
            if (s1->ele[i].j < s2->ele[i].j)
            {
                sum->ele[k++] = s1->ele[i++];
            }
            else if (s1->ele[i].j > s2->ele[i].j)
            {
                sum->ele[k++] = s1->ele[j++];
            }
            else
            {
                sum->ele[k] = s1->ele[i];
                sum->ele[k++] = s1->ele[i++].data + s2->ele[j++].data;
            }
        }
    }
}