Inverse of a Special Matrix and Application
Thuan Nguyen

arXiv:1708.07795v1 [cs.DM] 25 Aug 2017

School of Electrical and Computer Engineering, Oregon State University, Corvallis, OR, 97331
Email: nguyeth9@oregonstate.edu

Abstract—The matrix inversion is an interesting topic in
algebra mathematics. However, to determine an inverse matrix
from a given matrix is required many computation tools and
time resource if the size of matrix is huge. In this paper, we have
shown an inverse closed form for an interesting matrix which has
much applications in communication system. Base on this inverse
closed form, the channel capacity closed form of a communication
system can be determined via the error rate parameter α.

Keywords: Inverse matrix, convex optimization, channel
capacity.
I. M ATRIX C ONSTRUCTION
In Wireless communication system or Free Space Optical
communication system, due to the shadow effect or the turbulent of environment, the channel conditions can be flipped
from “good” to “bad” or “bad” to “good” state such as
Markov model after the transmission time σ [1] [2]. For
simple intuition, in “bad” channel, a signal will be transmitted
incorrectly and in “good” channel, the signal is received
perfectly. Suppose a system has total n channels, the “good”
channel is noted as “1” and “bad” channel is “0”, respectively,
the transmission time between transmitter and receiver is σ,
the probability the channel is flipped after the transmission
time σ is α. We note that if the system using a binary code
such as On-Off Keying in Free Space Optical communication,
then the flipped probability α is equivalent to the error rate.
Consider a simple case for n = 2, suppose that at the
beginning, both channel is “good” channel, the probability of
system has both of channels are “good” after transmission
time σ, for example, is (1−α)2 . Let call Aij is the probability
of system from the state has i − 1 “good” channels and
n − i + 1 “bad” channels transfers to state has j − 1 “good”
and n − j + 1 “bad” channels. Obviously that 1 ≤ i ≤ n + 1
and 1 ≤ j ≤ n + 1. For example, the transition matrix A2
and A3 for n = 2 and n = 3 are constructed respectively as
follows:
(1 − α)2

A2 = α(1 − α)
α2



(1 − α)3

(1 − α)2 α
A3 = 
(1 − α)α2
α3

2α(1 − α)
(1 − α)2 + α2
2α(1 − α)

3(1 − α)2 α
2(1 − α)α2 + (1 − α)3
2(1 − α)2 α + α3
3α2 (1 − α)


α2
α(1 − α) .
(1 − α)2

3α2 (1 − α)
2(1 − α)2 α + α3
2(1 − α)α2 + (1 − α)3
3(1 − α)2 α

given by Proposition 2. Moreover, this matrices are obviously
central symmetric matrix.
Proposition 1. For n channels system, the transition matrix
An has size (n + 1) × (n + 1) and all entries An ij in row i
column j will be established by
An ij =

s=max(i−j,0)

n+1−i

s

i−1


j−i+2s
n−(j−i+2s)
α
(1 − α)

Proof. From the definition, Anij is the probability from state
has i − 1 “good” channels or i − 1 bit “1” transfer to state has
j − 1 “good” channels or j − 1 bit “1”. Therefore, suppose
s is the number channels in i − 1 “good” channels that is
flipped to “bad” channels after the transmission time σ and
0 ≤ s ≤ i − 1. Thus, to maintain j − 1 “good” channels after
the time σ, the number of “bad” channels in n + 1 − i “bad”
channels must be flipped to “good” channels is:
(j − 1) − ((i − 1) − s) = j − i + s
Therefore, the total number of channels are flipped their
state after transmission time σ is:
s + (j − i + s) = j − i + 2s
and the total number of channels that preserves their state after
transmission time σ is n−(j −i+2s). However, 0 ≤ s ≤ i−1.
Similarly, the number of “bad” channels in n + 1 − i “bad”
channels must be flipped to “good” channels should be in
0 ≤ j − i + s ≤ n + 1 − i. Hence:
(
max s = min(n + 1 − j; i − 1)
min s = max(0; i − j)
Therefore, An ij can be determined by below form:
An ij =

 j − i + s 
s=min(n+1−j,i−1)
X
s=max(i−j,0)

n+1−i

s

i−1


j−i+2s
n−(j−i+2s)
α
(1 − α)

Proposition 2. All the entries of inverse matrix A−1
n given in
Proposition 1 can be determined via original transition matrix

A
n for ∀ α 6= 1/2.

α3

(1 − α)α2 
.
(1 − α)2 α
(1 − α)3

These transition matrices are obviously size (n+1)×(n+1)
since the number of “good” channels can achieve n+1 discrete
values from 0, 1, . . . , n. Moreover, these class matrices have
several interesting properties: (1) all entries in matrix An can
be determined by Proposition 1; (2) the inverse of matrix An is

s=min(n+1−j,i−1)
 j − i + s 
X

An −1
ij =

(−1)i+j
An
(1 − 2α)n ij

Due to the pages limitation, we will show the detailed
proof at the end of this paper. To illustrate our result, an
example of the inverse matrix A2 are shown as follows:

A−1
2


(1 − α)2
1

=
−α(1 − α)
(1 − 2α)2
α2

−2α(1 − α)
(1 − α)2 + α2
−2α(1 − α)


α2
−α(1 − α) .
(1 − α)2

Next, base on the existence of inverse matrix closed form,
we will show that a capacity closed form for a discrete
memory-less channel can be established. We note that in [3],
the authors said that haven’t closed form for channel capacity
problem. However, with our approach, the closed form can be
established for a wide range of channel with error rate α is
small.
II. O PTIMIZE SYSTEM CAPACITY

A discrete memoryless channel is characterized by a channel
matrix A ∈ Rm×n with m and n representing the numbers of
distinct input (transmitted) symbols xi , i = 1, 2, . . . , m, and
output (received) symbols yj , j = 1, 2, . . . , n, respectively.
The matrix entry Aij represents the conditional probability
that given a symbol xi is transmitted, the symbol xj is
received. Let p = (p1 , p2 , . . . , pm )T be the input probability
mass vector, where pi denotes the probability of transmitting
symbol xi , then the probability mass vector of output symbols
q = (q1 , q2 , . . . , qn )T = AT p, where qi denotes the probability
of receiving symbol yi . For simplicity, we only consider the
case n = m such that the number of transmitted input patterns
is equal the number of received input patterns. The mutual
information between input and output symbolsis:
I(X; Y ) = H(Y ) − H(Y |X),
where
H(Y ) =
H(Y |X) =

j=n
X

qj
j=1
m X
n
X

−

log qj

pi Aij log Aij .

i=1 j=1

Thus, the mutual information function can be written as:
I(X; Y ) = −

j=n
X

(AT p)j log (AT p)j +

m X
n
X

pi Aij log Aij ,

i=1 j=1

j=1

where (AT p)j denotes the jth component of the vector
q = (AT p). The capacity C of a discrete memoryless channel
associated with a channel matrix A puts a theoretical maximum rate that information can be transmitted over the channel
[3]. It is defined as:
C = max I(X; Y ).
p

(1)

Therefore, finding the channel capacity is to find an optimal
input probability mass vector p such that the mutual information between the input and output symbols is maximized.
For a given channel matrix A, I(X; Y ) is a concave function
in p [3]. Therefore, maximizing I(X; Y ) is equivalent to
minimizing −I(X; Y ), and the capacity problem can be cast
as the following convex problem:

Minimize:
m X
n
n
X
X
pi Aij log Aij
(AT p)j log (AT p)j −
i=1 j=1

j=1

Subject to:
(

pi  0
1T p = 1

Optimal numerical values of p∗ can be found efficiently
using various algorithms such as gradient methods [4] [5].
However, in this paper, we try to figure out the closed form for
optimal distribution p via KKT condition. The KKT conditions
state that for the following canonical optimization problem:
Problem Miminize: f (x)
Subject to:
gi (x) ≤ 0, i = 1, 2, . . . n,
hj (x) = 0, j = 1, 2, . . . , m,
construct the Lagrangian function:
L(x, λ, ν) = f (x) +

n
X
i=1

λi gi (x) +

m
X

νj hj (x),

(2)

j=1

then for i = 1, 2, . . . , n, j = 1, 2, . . . , m, the optimal point
x∗ must satisfy:


gi (x∗ ) ≤ 0,



∗


hj (x ) = 0,
dL(x,λ,ν)
(3)
|x=x∗ ,λ=λ∗ ,ν=ν ∗ = 0,
dx


∗ ∗

λi xi = 0,



λ∗ ≥ 0.
i

Our transition matrix that is already established in previous
part can represent as a channel matrix. In the optical transmission, for example, the transmission bits are denoted by the
different levels of energy, for example, in On-Off Keying code
bit “1” and “0” is represented by high and low power level.
This energy is received by a photo diode and converse directly
to the voltage for example. However, these photo diode work
base on the aggregate property when collecting all the incident
energy, that said, if two channels transmit a bit “1” then the
photo diode will receive the same energy “2” even though this
energy comes from a different pair of channels. Therefore,
the received signal is completely dependent to the number
of bits “1” in transmission side. Hence, in receiver side, the
photo diode will recognize n + 1 states 0, 1, 2, . . . , n. From
this property, the transition matrix A is the previous section
is exactly the system channel matrix. The channel capacity of
system, therefore, is determined as an optimization problem
in (1).
Next, we will show that the above optimization problem
can be solved efficiently by KKT condition. We note that
our method can establish the closed form for general channel
matrix and then the results are applied to special matrix
An . First, we try to optimize directly with input distribution

p, however, the KKT condition for input distribution is too
complicated to construct the first derivation. On the other hand,
base on the existence of inverse channel matrix, the output
variable is more suitable to work with KKT condition since.
Due to 0 ≤ qj ≤ 1, the Lagrange function from (2) with
output variable q is:

L(qj , λj , νj ) = I(X, Y ) +

j=n
X

j=n
X

qj λj + ν(

qj − 1)

j=1

j=1

Using KKT conditions, at optimal point qj∗ , λ∗j , ν ∗ :
 ∗
qj ≥ 0


Pj=n ∗




j=1 qj = 1


dI(X, Y )
ν ∗ − λ∗j −
=0
dqj∗



λ∗ ≥ 0



 j∗ ∗
λj qj = 0
P
Because 0 ≤ pi ≤ 1, i = 1, . . . , (n) and ni=1 pi = 1, so
Pi=n
always exist pi > 0. From qj = i=1 pi Aij with ∀ Aij > 0,
we can see clearly that qj > 0 with ∀qj or qj∗ > 0 with ∀qj∗ .
Therefore with fifth condition, λ∗j = 0 with ∀λ∗j . Then, we
have simplified KKT conditions:
Pj=n ∗
 j=1 qj = 1
dI(X, Y )
=0
ν ∗ −
dqj∗
The derivations are determined by:

j=n
i=n
dI(X, Y ) X −1 X
Aij log Aij − (1 + log qj )
Aji
=
dqj
j=1
i=1

Let call:

i=n
X

A−1
ji

j=n
X

Aij log Aij = Kj

From the second KKT simplified condition, we can compute ∀ qj∗ :
∗
qj∗ = 2Kj −ν −1
And finally:
∗

Due to the channel matrix is a closed form of α, the optimal
input vector p and output vector q also is a function of α.
However, we note that since the KKT condition works directly
to the output variable q, the optimal input p can be invalid
pi > 1 or pi < 0. In next step, our simulations shown that for
n ≤ 10 and α ≤ 0.2, both output and input vector are valid.
That said, our approach will be worked with a good system
where the error probability α is small. In case of the invalid
optimal input vector, the upper bound of channel capacity, of
course, will be established.
III. C ONCLUSION
In this paper, our contributions are twofold: (1) establish an
inverse closed form for a class of channel matrix based on the
error probability α; (2) figure out the closed form for channel
matrix with small error rate α and determine the upper bound
system capacity for a high error rate channel.
R EFERENCES
[1] Jeff McDougall and Scott Miller. Sensitivity of wireless network
simulations to a two-state markov model channel approximation. In
Global Telecommunications Conference, 2003. GLOBECOM’03. IEEE,
volume 2, pages 697–701. IEEE, 2003.
[2] Hong Shen Wang and Nader Moayeri. Finite-state markov channel-a
useful model for radio communication channels. IEEE transactions on
vehicular technology, 44(1):163–171, 1995.
[3] Thomas M Cover and Joy A Thomas. Elements of information theory.
John Wiley & Sons, 2012.
[4] Michael Grant, Stephen Boyd, and Yinyu Ye. Cvx: Matlab software for
disciplined convex programming, 2008.
[5] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

j=1

i=1

A PPENDIX

Next, using derivation of I(X,Y) at qj = qj∗ and last KKT
condition:
ν ∗ = Kj − (1 + log qj ∗ )
Hence:
qj∗ = 2Kj −ν

∗

−1

Next, using first KKT simplified condition, we have the
sum of all output states is 1.
j=n
X

2Kj −ν

∗

−1

=1

j=1

2

ν∗

=

j=n
X

2

Kj −1

j=1

Therefore, ν ∗ can be figured out by:
∗

∗

pT = q T A−1
ij

ν = log

j=n
X
j=1

2Kj −1

Proof for Proposition 2.
Proof. To simplify our notation, the “good” and “bad” channel
are represented by bit “1” and “0”, respectively. Next, we will
use the definition to show that:
An An −1 = I
If matrix A∗n is constructed by A∗nij = (−1)i+j An ij , then
we need to show that:
An A∗n = B = (1 − 2α)n I
Firstly, we note that the An ij and An ∗ij is only different
by sign of the first index (−1)i+j . Therefore, Bij which is
computed by product of row i in matrix An ij and column j
in matrix An ∗ij , can be computed by:
Bij =

k=n+1
X
k=1

An ik A∗nkj

Note that the An ik is the probability from state i “good”
channels (with i − 1 bit “1” and n − i + 1 bit “0”) to medium
state has k “good” channels (with k − 1 bit “1” and n − k + 1
bit “0”). Moreover, if the sign is ignored, then An ∗kj also is
the probability going from state
k to state j, too. However,

n
the state k includes C k−1
sub-states which have a same
number of “good” and “bad” channels. For example with
n = 2, state k = 2 includes two sub-states that contains one
“good” and one “bad” channels are “10” an “01”. Therefore,
the total number of sub-states while k runs from 1 to n is
P
k=n+1
n
C k−1
= 2n sub-states. Let compute Bij by divided
k=1
into two subsets:
Compute Bij for i = j: This means that Bii is the sum
of the probability from state i − 1 bit “1” go to states has
k − 1 bit “1” then come back to state has i − 1 bit “1”. In
2n sub-states, we can divide back to n + 1 categories by the
number of different position between i and k.
• If all the bit in i and k are the same, then the probability
is:
!
!
C

n
n
(1 − α)2n
(1 − α)n (1 − α)n = C
0
0

• If all the bit in i and k different at only one position, then
the probability is:
!
n
(1 − α)2(n−1) (1 − α)2
C
1

• If all the bit in i and k different at only two positions,
then the probability is:
!
n
C
(1 − α)2(n−2) (1 − α)2×2
2

• If all the bit in i and k different at all positions, then the
probability is:
!
C

n
(1 − α)2n
n

Therefore, Bii can be determined by the probability of all
n + 1 categories such as:
!
n 2t
C
α (1−α)2n−2t = ((1 − α)2 − α2 )n = (1−2α)n
Bii =
t
t=0
t=n
X

A∗nkj

into two subsets:
Compute Bij for i6= j: Let divide
k + j is odd and A∗nkj < 0 or k + j is even and A∗nkj > 0,
Pk=n
respectively. Therefore, Bij = k=1 An ik A∗nkj also is distributed into positive or negative subsets. Next, we will show
that the positive subset in Bij is equal the negative subset then
Bij = 0 for i 6= j. Indeed, suppose that state i with i − 1 bit
“1” go to state k1 and then to back to state j with j −1 bit “1”
and Bik1 is positive value. Next, we will show that existence
a state k2 such that Bik2 is negative value and Bik1 = −Bik2 .
Let call s is the number of positions where state i and j
have a same bit. Obviously that s ≤ n − 1 due to i 6= j. For
example if n = 4 and i = 1111 and j = 0001, we have s = 1
because i and j share a same bit “1” in the positions fourth.
Suppose that an arbitrary state k1 are picked, we will show

how to chose the state k2 with Bik1 = −Bik2 . Consider two
follows cases:
• If (n − s) is odd. k2 is constructed by maintain s position
of k1 where i and j have same bit and flip bit in the n − s
rest positions.
• If (n − s) is even. k2 is constructed by maintain s + 1
position of k1 where s position are i and j have a same bit and
one position where i and j have a different bit, next n − s − 1
rest positions will be flipped. Note that since s ≤ n − 1 then
we are able to flip n − s − 1 rest positions.
We obviously can see that k1 and k2 satisfied the probability
condition |Bik1 | = |Bik2 | due to the number of flipped bit
between i and k1 equals the number of flipped bit between k2
and j and the number of flipped bit between j and k1 equals
the number of flipped bit between k2 and i.
Next, we will prove that k1 and k2 make Bik1 and Bik2 in
different subsets. Indeed, call number of bit “1” in k1 is b1 ,
number of bit “1” in k2 is b2 , number of bit “1” in s bit same
of i and j is bs , respectively. Therefore, the number of bit “1”
of k1 in (n − s) rest positions is (k1 − ks ), the number of bit
“1” of k2 in (n − s) rest positions is (k2 − ks ).
• If (n − s) is odd. Since all bit in (n − s) rest positions
of k1 is flipped to create k2 , then total number of bit “1” in
n − s bit of k1 and k2 is (k1 − ks + k2 − ks = n − s) is odd.
So, (k1 + k2 ) should be an odd number. That said (k1 − k2 )
is odd or (k1 + j) − (k2 + j) is odd. Therefore, Bik1 and Bik2
bring the contradict sign.
• If (n − s) is even. Because, we fix one more position to
create k2 , then number of flipped bit (n−s−1) is odd number.
If one more bit is fixed in k1 is “0”, we have a same result
with case (n − s) is odd. If fixed bit is “1”, similarly in first
case (k1 − ks − 1) + (k2 − ks − 1) = n − s − 1 is odd number,
therefore (k1 + k2) is odd number. That said (k1 − k2 ) is odd
or (k1 + j) − (k2 + j) is odd. Therefore, Bik1 and Bik2 bring
the contradict sign.
Therefore, the state k2 always can be created from a random
state k1 and Bik1 and Bik2 bring a contradict sign. That said
for i 6= j, Bij = 0. Therefore:
B = (1 − 2α)n I
The Proposition 2, therefore, are proven.

