
11.8 The Powers of a Matrix

Direct relations between pair of nodes are expressed by corresponding entries in graph matrix. However, practical applications require representation of indirect relations that exist by virtue of intermediate nodes that exist between the two nodes of our interest. The powers of a matrix representation are very much useful in representing indirect relation between two nodes.

In order to represent an indirect relation that is assumed to be transitive between two nodes a and b via one intermediate node, we can square the matrix. Here you can notice that the square of the matrix represents all path segments that are two links long.

Similarly, transitive relation between two nodes a and b via two intermediate nodes is represented by 3 power of the matrix. Here 3 power of the matrix represents all path segments that are three links long.

If we proceed in this manner, we can obtain n1 power of the matrix. If a graph has n nodes then there are at the maximum n1 links. Thus for a graph with n nodes, at the maximum, we can go up to n1 power of the matrix. Also, by representing concatenation of links by multiplication and parallel links by addition, we can represent the set of all paths of matrix A whose entries are aij between any node i and any other node j (possibly i itself) ova all possible nodes


11.8.1 Matrix Powers and Products

For a given matrix A whose entries are aij , the square of the matrix is obtained by replacing every entry with


Let us consider a more general case where we want to arrive at product of two matrices A and B with entries a_{ik} and b_{kj}.

In order to arrive at matrix C which is product of A and B , we calculate each entry c_{ij} in matrix C by combining ith row of matrix A with jth column of matrix B. That is, we arrive at entry c_{ij} as follows:


Here entries in matrix C are arrived at as follows:
c11 = a11b11 + a12b21 + a13b31 + a14b41
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
b11 b12 b13 b14
b21 b22 b23 b24
b31 b32 b33 b34
b41 b42 b43 b44
c11 c12 c13 c14
c21 c22 c23 c24
c31 c32 c33 c34
c41 c42 c43 c44
c12 = a11b12 + a12b22 + a13b32 + a14b42
c13 = a11b13 + a12b23 + a13b33 + a14b43
...........................................
...........................................
c23 = a21b13 + a22b23 + a23b33 + a24b43
..........................................................................
.........................................................................
C44 = a41b14 + a42b24 + a43b34 + a44b44
Example:
Let us consider matrix A.


Then, we can calculate A2 as follows:


In order to arrive at matrix with higher powers, we can use Associative Property. Matrix multiplication is associative provided underlying relation arithmetic is associative. This property can be effectively used in order to perform multiplication to arrive at matrix with higher powers.

Using this Associative Property, we can write:
A^{3} = AA^{2} = A^{2}A
A^{4} = A A^{3} = A^{3}A= A^{2} A^{2}





Khannur's Book 

Arunkumar Khannur, Software Testing  Techniques and Applications,
Published by Pearson Publications, 2011
(ISBN:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO Forum

Contact Khannur 
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block,
Rajajinagar,
Bangalore  560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt 
