Arunkumar Khannur's Software Testing Knowledge Center
   
 

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 n-1 power of the matrix. If a graph has n nodes then there are at the maximum n-1 links. Thus for a graph with n nodes, at the maximum, we can go up to n-1 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 aik and bkj.

In order to arrive at matrix C which is product of A and B , we calculate each entry cij in matrix C by combining ith row of matrix A with jth column of matrix B. That is, we arrive at entry cij 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:
A3 = AA2 = A2A
A4 = A A3 = A3A= A2 A2
 
 
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
         
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
STEP-AUTO 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