Applications of Symmetric Circulant Matrices to Isotropic Markov Chain Models and Electrical Impedance Tomography ()
1. Introduction
Electrical impedance tomography (EIT) and electrical capacitance tomography (ECT) are emerging engineering modalities designed to solve inverse problems by measuring electric signals on the periphery of the body and reconstructing the electromagnetic properties within the body. In its simplest 2D disk form, the problem reduces to relation of vector of voltages to vector of currents through a matrix, as in Ohm’s law. It was proven that this Ohm’s matrix is symmetric circulant. Although some properties of these matrices have been recently men- tioned in several papers including [1] and [2] , no systematic study has been conducted including computation of eigenvectors and eigenvalues. The problem of computation of the elements of symmetric circulant matrix with equidistant electrodes gives rise to a new special function. We also suggest application of symmetric circulants to model very special isotropic Markov chains.
2. Properties Overview
In a symmetric Toeplitz matrix, the elements of diagonal parallel to the main diagonal are the same. A circulant matrix, or shortly circulant, is a special Toeplitz matrix which does not change upon forward shift of its elements; a concise discussion of circulant matrices and their properties is found in [3] [4] . In the matrix form, we can express the shift as multiplication by a permutation matrix [5] . The
shift matrix
is such that
for
and 0 elsewhere. For example, the 4 ´ 4 shift matrix
has the form
(1)
Davis [5] proves that a square matrix
is circulant if and only if
or equivalently
(2)
Hereafter bold upper case is used for matrices and bold lowcase is used for vectors. The elements of a
circulant matrix are defined by the
ele- ments in the first row. The following properties of circulant matrices are well known: 1) A linear combination of circulants is a circulant, 2) the product of circulants is a circulant, 3) the inverse of a circulant is a circulant, 4) circulants have the same eigenvectors, 5) circulants commute. The proof and other pro- perties of circulants can be found in the books cited above.
The object of the present paper is symmetric circulant matrix, or shortly Symmetric Circulant (SC). This very special class of Toeplitz matrices sometimes emerge in problems of discrete periodic convolutions with symmetric/spherical kernel [6] [7] . The properties of SC are scattered through the literature; below we summarize these properties with emphasis on the computation of their eigenvalues and eigenvectors.
Below are examples of SC matrices for
and 6.
Since a SC matrix is Toeplitz and symmetric, the elements parallel to the main diagonal are the same on both sides of the diagonal. Since a SC matrix is cir- culant, each row is constructed by the left shift of the previous row: the last element of the previous row moves to the first column with the rest of elements from the previous row to follow. The following theorem collects peculiar pro- perties of a SC matrix (the proof is either elementary or can be found elsewhere).
Theorem 1. The following holds:
1) The sum of elements in each row and column of a SC matrix is the same.
2) A linear combination of SC matrices is a SC matrix.
3) The inverse of a SC matrix is a SC matrix.
4) The product of SC matrices is a SC matrix.
5) Matrix
is SC if and only if
and the sum of elements in each row is the same.
6) The
SC matrix is defined by
distinct elements, where
denotes the closest larger integer.
7) SC matrices of the same size have the same eigenvectors.
8) SC matrices commute, namely, if T1 and T2 are SC matrices, then
.
Eigenvalues and Eigenvectors of Symmetric Circulant
The eigenvalues and eigenvectors of SC matrices are real because the matrix is symmetric. If
are the elements in the first row then the eigenvalues are expressed as a linear combination:
(3)
Using elementary trigonometry one can show that for an even
the largest and the smallest eigenvalues are unique, but the rest repeat twice. For an odd
the largest eigenvalue is unique but the rest repeat twice. The last eigenvalue
corresponds to the eigenvector
. As follows from the previous theorem
so the number of unique eigenvalues is
As was shown in [6] and [8] the
th eigenvector corresponding to the eigen- value (3) of any symmetric circulant matrix is
(4)
where
. These vectors have unit norm and are pair wise orthogonal. As a word of caution, several authors including [9] and [10] , mis- takenly reported the formula for the eigenvectors proportional to
. The adjustment
in formula (4) is due to the presence of repeated eigen- vectors in symmetric circulants. Many properties of SC matrices, such as those listed in Theorem 1, follow from the fact that SC matrices have the same eigen- vectors provided by formula (4).
3. Applications
The symmetric circulant matrix is not just a curious mathematical object; it has several applications. For example, a SC matrix is used in physical applications [6] and image processing to describe the Karhunen-Loève type rotations of image templates [9] [11] . Generally, the SC matrix may be useful in modeling rotation- invariant systems in equilibrium. This claim is illustrated by the following example.
3.1. Isotropic Markov Chain
The Markov chain model describes a stochastic process,
, where each random variable
at time t may be in one of
states
. In a Markov chain, the probability distribution at time t is completely specified at time
; in other words,
. The con- ditional probabilities are called transition probabilities,
which reads as the probability to move to state
given that at the previous time it was at state
. Note that these probabilities do not depend on time
. There are many excellent books on Markov chain models, see [12] [13] [14] among them.
Definition 2. A Markov chain model is called isotropic if the transition pro- bability,
, is a function of
.
The transition probability matrix of an isotropic Markov chain is symmetric and consequently doubly stochastic. That is, the sum of elements in each column is 1. An Isotropic Markov chain can be used to describe a random walk on the circle or globe as a model for virus or rumor spread. To be specific, we talk in terms of a random walk. Let
points/states be specified by
vector co- ordinates
. We assume that the probability,
, of walking from state
to state
is a function of the distance
. A natural assump- tion is that
is a decreasing function of the distance. Clearly, the transition- probability matrix is specified by
numbers
Theorem 3. The matrix of transition probabilities of an isotropic Markov chain model is a symmetric circulant matrix.
Proof. We simply refer to Theorem 1 #5 noting that the sum of elements in each row is 1, which also holds for the sum of any exhaustive set of probabilities.
An important question is the stationary state of an isotropic Markov chain, the probability distribution of each state after an infinite number of steps, the long-run behavior of Markov chain,
,
. These probabilities are called stationary probabilities.
Theorem 4. The stationary probability distribution of an isotropic Markov chain with positive transition probabilities is uniform,
.
Proof. The long-run (stationary) vector-row probability,
, is the solution to the equation
, where
is the
matrix of transition probabilities [15] . Since
is symmetric for an isotropic Markov chain, we conclude that
is the eigenvector corresponding to the eigenvalue 1. Since
for all
, it follows from (3) that the maximum eigenvalue is unique with
:
The eigenvector correspond- ing to this value is
which means that the probability of stepping to each state is the same,
. In fact, one can prove that the stationary probabilities are the same if the matrix of transition probabilities is symmetric.
Using the previous interpretation with a virus epidemic on the globe, if the probability of infection is positive for each pair of locations
, sooner of later all people get infected with equal probability.
3.2. Laplace Equation on a Disk and Generalized Ohm’s Law
The symmetric circulant matrix appears in Ohm’s law on a disk. From ele- mentary physics, we know that by Ohm’s law the difference of voltages at the ends of a wire,
, is the product of the resistivity of the wire,
, and the current
,
(5)
What is Ohm’s law on a disk when
currents and voltages are measured at a finite number of electrodes on the perimeter? Apparenly, the vectors of vol- tages and currents must be connected through a
matrix with
as the resistivity coefficient since the disk is homoheneous. We term this matrix the Ohm’s matrix, and as we show below this matrix is symmetric circulant if electrodes are placed at angles
,
where
is any.
The following formulation may be viewed a simplified scheme of electrical impedance tomography (EIT), when electromagnetic properties, such as re- sistivity and permittivity within the body, are reconstructed from measurements of current and voltage on the periphery of the body; more detail can be found in [16] [17] [18] [19] .
We consider a homogeneous disk with resistivity
of radius
. The cur- rent is applied at the circle with density
,
. The system is in equilibrium, so we have
. The resulting voltage
, as a function of radius
and angle
, in polar coordinates is governed by a Laplace equa- tion:
(6)
with the Neumann boundary condition
In reality, the current is applied at a finite number of electrodes and is zero elsewhere on the circle. Typically
electrodes (usually an even number) are located on the circle centered at angles
,
with the same half-width,
, measured in radians (the width of the electrodes is fairly small, so they do not overlap). To simplify, we shall assume that the current density flux is uniform over the electrode (the so called shunt model [20] ). These assumptions specify the step function
as follows.
As shown in [1] , the potential
at angle
and distance
from the center in the finite-electrode EIT system is given by the equation
(7)
Two examples of potential distribution on a disk using this formula is shown in Figure 1 with
,
and
All currents are the same in absolute value but differ in sign (the inward arrows indicate negative current and the outward arrows indicate the positive current). In the example at left, the currents at the opposite electrodes have the opposite sign and in the example at right the currents are the same. Clearly, the two current scenarios create quite different voltage distributions in the disk.
In Ohm’s law, we relate the voltage and current on the periphery of the conductor. From (7), we derive how voltages and currents at the electrodes are related, letting
and
, which yields
where
is the current at electrode
(the integral of the current density over the width of the electrode), and
is the
vector of currents.
Finally, in the matrix form, Ohm’s law on a homogeneous disk with re- sistivity
and
equidistant electrodes placed at angles
for
is given by
(8)
where
is the
matrix with entries
(9)
Compared to Ohm’s law on a wire (5), Ohm’s law on a disk (8) contains an
matrix. This matrix (9) will be referred to as the Ohm’s matrix because it relates the vectors of voltages and currents. Below, we prove that this matrix is symmetric circulant.
Theorem 5. The
Ohm’s matrix with elements specified by (9) is a symmetric circulant matrix.
Proof. It is easy to see that T is symmetric. The fact that the sum of elements in each row is constant follows from the fact that
is an even function and
the sum
does not depend on
. To prove this we note that (a)
Figure 1. The voltage distribution on a homogeneous disk with four electrodes (shown on the circle as wide black segments). Arrows indicate the current supplied at the elec- trodes: All currents are the same but differ by sign. The inward arrows indicate negative and the outward arrows indicate positive current.
and (b) the set of unique values of
does not depend on
and equal
. Therefore, we deduce that
and does not depend on
. Since
is a function of
, as follows from Theorem 1 #4, matrix (9) is a SC matrix.
The Ohm’s law matrix posesses unique properties and have been studied previously in connection with electrical impedance tomography [1] [21] [22] [23] . As we know from the previous section, there are
unique elements of matrix
, denoted
. Their computation gives rise to a new special function, defined below.
Definition 6. Function
(10)
(11)
is called the D-function.
Note that we provide two forms of the function: the first is through Fourier series and the second is through an integral. The equality comes from a known fact:
after integration from 0 to
. Interestingly, mathematics reference books list pairs of functions that are close in terms of expressions, but not this one. To the best of our knowledge, the
- function cannot be easily expressed as other known special functions. This function takes zero values at 0, 1/2 and 1 and is odd around
. It is elementary to show that it takes its maximum at
and mini- mum at
By direct examination, it is easy to see that
(12)
For example, when the number of electrodes
, we have that matrix
(13)
is completely specified by 5 unique elements. In Figure 2, we show this matrix as an image with
at left and values of
with
, 0.1 and 0.2.
When
, we can roughly approximate
with the identity matrix, so the disk and wire Ohm’s laws become virtually equivalent. The diagonal ele- ments of the SC matrix are dominant. There is a weak dependence of
on
for
.
The SC matrix reflects the physical principals of Ohm’s law on a disk with equidistant electrodes:
1) It does not matter how the electrodes are indexed (i.e., which electrode is #1) because matrix
is circulant.
2) Ohm’s law (8) can be rewritten as
, where
is conductivity because matrix
is a SC matrix.
3.3. Resistivity Estimation in a Homogeneous Tank
In this section, we apply the generalized Ohm’s law on a disk to reconstruct the
Figure 2. Matrix (13) shown as an image and unique t elements with three values of ω.
Figure 3. Left panel: EIT experiment with tank filled with gelatin. The current is injected at 16 equally spaced electrodes (color of clips does not matter). The voltage is measured at the same electrodes, 15 current patterns are applied with 17 frequencies. Right panel: Estimation of resistivity of gelatin using the generalized Ohm’s law on a disk with standard error bars.
electric resistivity of gelatin in the lab tank using EIT hardware (see Figure 3). Currents are injected at
equally spaced electrodes with 17 different fre- quencies varying from 10 KHz to 3359 KHz. The diameter of the tank was 20 cm and the width of each electrode was 1 cm, so
radian (the 16 electrodes cover about
of the tank circle). For each frequency, 15 sinu- soidal patterns (vectors) of currents are injected and the resulting voltage is measured; more detail about the hardware design is found in [24] .
Let
and
be 16 ´ 15 matrices of voltage and current (the
th column of
is the
th pattern). Then, by Ohm’s law, the matrix of voltages can be expressed as a linear regression model with an unknown coefficient,
where
is the 16 ´ 15 matrix with independent and identically distributed error elements with zero mean and constant variance
. A least squares esti- mate of
minimizes
and can be written in matrix form as
The estimate of the variance is
where
is an unbiased estimate of
[25] . The results of estimation of the gelatin resistivity with
bars for 17 frequencies estimated separately are shown in the right panel of Figure 3. Note that 1) the resistivity estimate drops with increasing frequency and 2) the uncertainty of resistivity estimation (SE) is about 1 cm/S.