Matrix (Level- 1)

1. Properties of matrix

A matrix represents a collection of numbers arranged in order of rows and columns. 
It is necessary to enclose the elements of a matrix in parentheses or brackets.

A matrix with 9 elements is shown below:

The above Matrix M has 3 rows and 3 columns. Each element of matrix [M] can be referred to by 
its row and column number. For example, M23 = 6

Order of a Matrix : The order of a matrix is defined in terms of its number of rows and columns.


Order of a matrix = No. of rows × No. of columns

Therefore, Matrix [M] is a matrix of order 3 × 3.




Transpose of a Matrix


The transpose [M]T of an m x n matrix [M] is the n x m matrix obtained by interchanging the rows and columns of [M].

Transpose of a matrix A is defined as:


if A= [aij] mxn:
    then AT = [bij] nxm where bij = aji


For Example, transpose of matrix M, MT will be:


M = 1 2 3
      4 5 6
      7 8 9


MT  = 1 4 7
         2 5 8
         3 6 9


Properties of transpose of a matrix:


(AT)T = A
(A+B)T = AT + BT
(AB)T = BTAT




Properties of Matrix addition and multiplication:


A+B = B+A (Commutative)
(A+B)+C = A+ (B+C) (Associative)
AB ≠ BA (Not Commutative)
(AB) C = A (BC) (Associative)
A (B+C) = AB+AC (Distributive)




Terminologies


Square Matrix: A square Matrix has as many rows as it has columns. i.e. no of rows = no of columns.
Symmetric matrix: A square matrix is said to be symmetric if the transpose of original matrix
 is equal to its original matrix. i.e. (AT) = A.
Skew-symmetric: A skew-symmetric (or antisymmetric or antimetric[1]) matrix is a square 
matrix whose transpose equals its negative.i.e. (AT) = -A.
Diagonal Matrix:A diagonal matrix is a matrix in which the entries outside the main diagonal 
are all zero. The term usually refers to square matrices.
Identity Matrix:A square matrix in which all the elements of the principal diagonal are ones 
and all other elements are zeros.Identity matrix is denoted as I.
Orthogonal Matrix: A matrix is said to be orthogonal if AAT = ATA = I.
Idemponent Matrix: A matrix is said to be idemponent if A2 = A.
Involutary Matrix: A matrix is said to be Involutary if A2 = I.
Singular Matrix: A square matrix is said to be singular matrix if its determinant is zero i.e. |A|=0
Nonsingular Matrix: A square matrix is said to be non-singular matrix if its determinant is non-zero.


Note: Every Square Matrix can uniquely be expressed as the sum of a symmetrix matrix 
and skew symmetric matrix. A = 1/2 (AT + A) + 1/2 (A - AT).


Trace of a matrix: trace of a matrix is denoted as tr(A) which is used only 
for square matrix and equals the sum of the diagonal elements of the matrix. F

2. Representation of matrix

// C++ code to demonstrate 2D vector 
#include <iostream> 
#include <vector> // for 2D vector 
using namespace std; 

int main() 
{ 
    // Initializing 2D vector "vect" with 
    // values 
    vector<vector<int> > vect{ { 1, 2, 3 }, 
                               { 4, 5, 6 }, 
                               { 7, 8, 9 } }; 

    // Displaying the 2D vector 
    for (int i = 0; i < vect.size(); i++) { 
        for (int j = 0; j < vect[i].size(); j++) 
            cout << vect[i][j] << " "; 
        cout << endl; 
    } 

    return 0; 
}

3. Matrix Operation

//addition
#include <bits/stdc++.h>
using namespace std;

int main(){

int N = 2, M = 2;
int m1[N][M] = { { 1, 2 },
                  { 4, 5 } };
int m2[N][M] = { { 5, 6 },
                  { 8, 9 } };
int ans[N][M];

// Traversing number of Rows
for(int i = 0; i < N; i++) 
{   
    // Traversing number of Columns  
    for (int j = 0; j < M; j++) 
    { 
        ans[i][j] = m1[i][j] + m2[i][j];
    } 
}

for (int i = 0; i < N; i++) 
{    
    for (int j = 0; j < M; j++) 
    { 
        cout<<ans[i][j]<<" ";
    } 
    cout<<endl;
 }

}
//subtarction
#include <bits/stdc++.h>
using namespace std;

int main(){

int N = 2, M = 2;
int m1[N][M] = { { 5, 6 },
                  { 8, 9 } };
int m2[N][M] = { { 1, 2 },
                  { 4, 5 } };
int ans[N][M];

// Traversing number of Rows
for(int i = 0; i < N; i++) 
{   
    // Traversing number of Columns  
    for (int j = 0; j < M; j++) 
    { 
        ans[i][j] = m1[i][j] - m2[i][j];
    } 
}

for (int i = 0; i < N; i++) 
{    
    for (int j = 0; j < M; j++) 
    { 
        cout<<ans[i][j]<<" ";
    } 
    cout<<endl;
 }

}
//multiplication
#include <bits/stdc++.h>
using namespace std;

int main(){

int M = 2, N = 2, P = 2;
int m1[M][N] = { { 5, 6 },
                  { 8, 9 } };
int m2[N][P] = { { 1, 2 },
                  { 4, 5 } };
int ans[M][P];

// Traversing number of Rows
for(int i = 0; i < M; i++) 
{   
    // Traversing number of Columns  
    for (int j = 0; j < P; j++) 
    { 
        ans[i][j] = 0;

        for( int k = 0; k < N; k++ )
            ans[i][j] += m1[i][k] * m2[k][j];
    } 
}

for (int i = 0; i < N; i++) 
{    
    for (int j = 0; j < M; j++) 
    { 
        cout<<ans[i][j]<<" ";
    } 
    cout<<endl;
 }

}

4. transpose of matrix

#include <bits/stdc++.h> 
using namespace std;

int main() 
{ 
    int n; 
    cin >> n;

    vector<vector<int>> vec(n, vector<int> (n, 0));
    vector<vector<int>> ans(n, vector<int> (n, 0));

    for(int i = 0; i < n ;i++){
        for(int j = 0; j < n; j++){
            int t;
            cin >> t;
            vec[i][j] = t;
        }
    }

    for(int i = 0; i < n ;i++){
        for(int j = 0; j < n; j++){
            cout << vec[i][j] << " ";
        }
        cout << "\n";
    }

    for(int i = 0; i < n ;i++){
        for(int j = 0; j < n; j++){
            ans[i][j] = vec[j][i];        
        }
    }

    cout << "\n\nTranspose: \n\n";

    for(int i = 0; i < n ;i++){
        for(int j = 0; j < n; j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }

    return 0; 
}

5. Median of row-wise sorted matrix

// C++ program to find median of a matrix
// sorted row wise
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100;

// function to find median in the matrix
int binaryMedian(int m[][MAX], int r ,int c)
{
    int min = INT_MAX, max = INT_MIN;
    for (int i=0; i<r; i++)
    {
        // Finding the minimum element
        if (m[i][0] < min)
            min = m[i][0];

        // Finding the maximum element
        if (m[i][c-1] > max)
            max = m[i][c-1];
    }

    int desired = (r * c + 1) / 2;
    while (min < max)
    {
        int mid = min + (max - min) / 2;
        int place = 0;

        // Find count of elements smaller than mid
        for (int i = 0; i < r; ++i)
            place += upper_bound(m[i], m[i]+c, mid) - m[i];
        if (place < desired)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}

// driver program to check above functions
int main()
{
    int r = 3, c = 3;
    int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} };
    cout << "Median is " << binaryMedian(m, r, c) << endl;
    return 0;
}