Home Previous year paper Algorithms Notes About us

Quick Links

Data Structure

Advanced Data Structure

Algorithms

Matrix

A matrix is composed of numbers in two dimensions: rows and columns. It is similar to a data table composed only of numbers. A member is identified by two indices, one for rows and another for columns. Entire rows or columns can be selected, deleted, concatenated, comparisons or inquiries performed.

Traversal of Matrix

Two common ways of traversing a matrix are row-major-order and column-major-order.
Row Major Order : When matrix is accessed row by row.
Column Major Order : When matrix is accessed column by column.

Example:

Input:

int arr[MAX][MAX] = { {1,2,3,4,5},{6,7,8,9,0},
{5,4,3,2,1},{0,0,0,0,0},
{8,9,7,6,1}};

Output:

Row Major Traversal
1 2 3 4 5
6 7 8 9 0
5 4 3 2 1
0 0 0 0 0
8 9 7 6 1
Column Major Traversal
1 6 5 0 8
2 7 4 0 9
3 8 3 0 7
4 9 2 0 6
5 0 1 0 1

Matrices Addition –

The addition of two matrices A m*n and Bm*n gives a matrix Cm*n. The elements of C are sum of corresponding elements in A and B which can be shown as:

Algorithm

for i in 1 to m
for j in 1 to n
cij = aij + bij

Matrices Subtraction –

The subtraction of two matrices Am*n and Bm*n gives a matrix Cm*n. The elements of C are difference of corresponding elements in A and B which can be represented as:

Algorithm

for i in 1 to m
for j in 1 to n
cij = aij-bij

Matrices Multiplication –

The multiplication of two matrices Am*n and Bn*p gives a matrix Cm*p. It means number of columns in A must be equal to number of rows in B to calculate C=A*B. To calculate element c11, multiply elements of 1st row of A with 1st column of B and add them (5*1+6*4) which can be shown as:

Algorithm

for i in 1 to m
for j in 1 to p
cij = 0
for k in 1 to n
cij += aik*bkj

Sparse Matrix

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example:

0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).

Practice Problems On Matrix