Linear Algebra in Engineering: Analyzing Networks with Adjacency Matrices (Part 4 of 7)

Preface
This series is aimed at providing tools for an electrical engineer to analyze data and solve problems in design. The focus is on applying linear algebra to systems of equations or large sets of matrix data.

Introduction
This article will demonstrate the use of adjacency matrices to analyze interconnected vertices (for example map or network data).

If you are not familiar with linear algebra or need a brush up I recommend Linear Algebra and its Applications by Lay, Lay and McDonald. It provides an excellent review of theory and applications.

This also assumes you are familiar with Python or can stumble your way through it.

The data and code are available here: linear4.py and linear4.xlsx.

Concepts
Adjacency Matrix: an nxn matrix where a '1' is placed when two vertices are immediately connected and a '0' when they are not.

Importing Your Data Set
I will use the Anaconda package suite with Python, numpy and the Spyder IDE for mathematical analysis. It is cross platform, free and open source. It is also easy to import data from Excel once you have the code snippet.

I usually have the following boilerplate code in my scripts:

import sys
import xlrd
import numpy as np
import matplotlib.pyplot as plt
from scipy.interpolate import interp1d


np.set_printoptions(threshold=np.nan)
print sys.version
print __name__


In this example I have fabricated a 6 x 6 network:


filename='linear_4.xlsx'
print
print 'Opening',filename
ss=xlrd.open_workbook(filename,on_demand=True)
sheet_index=0
print ' Worksheet',ss.sheet_names()[sheet_index]
sh=ss.sheet_by_index(sheet_index)



print ' Reading data values'
xa=[]
for row_index in range(0,sh.nrows):
row_single=[]
for col_index in range(0,sh.ncols):
row_single.append(sh.cell_value(row_index,col_index))
xa.append(row_single)
xa=np.matrix(xa)
print ' Design x array size:',len(xa)
print
print 'Adjacency Matrix:'
print xa


Here we read in a matrix of unknown size from Excel. If the array is large you should comment the print statements.

The last bit of code converts the array to a numpy matrix which will be necessary for the code below. Please note that numpy arrays are preferred and used in all my other posts. But the convenience of 'x*y' is very handy here and the '*' operator is not supported in numpy arrays the way you think it would be.

Finding n-distance Vertices
Now that the test results and input variables have been imported evaluating the number of possible paths between any two vertices is straight forward.

The number of steps is simply M^k where 'k' is the number of steps you are testing.


k=2
nt=xa**2
print 'For ',k,' points:'
print nt


This is the output:

2.7.11 |Anaconda 2.5.0 (64-bit)| (default, Jan 29 2016, 14:26:21) [MSC v.1500 64 bit (AMD64)]
__main__


Opening linear_4.xlsx
Worksheet Sheet1
Reading data values
Design x array size: 6


Adjacency Matrix:
[[ 0. 1. 0. 0. 0. 0.]
[ 1. 0. 1. 0. 1. 0.]
[ 0. 1. 0. 0. 0. 1.]
[ 0. 0. 0. 0. 0. 0.]
[ 0. 1. 0. 0. 0. 1.]
[ 0. 0. 1. 0. 1. 1.]]


For 2 points:
[[ 1. 0. 1. 0. 1. 0.]
[ 0. 3. 0. 0. 0. 2.]
[ 1. 0. 2. 0. 2. 1.]
[ 0. 0. 0. 0. 0. 0.]
[ 1. 0. 2. 0. 2. 1.]
[ 0. 2. 1. 0. 1. 3.]]


Next Up
In the next article we will examine production models in macroeconomics with Leontief Input-Output models.