# A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming
Problems

Vijay K. Garg
Department of Electrical and Computer Engineering
University of Texas at Austin,
Austin, TX 78712
<EMAIL_ADDRESS>

###### Abstract

It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm
solves many combinatorial optimization problems such as the shortest path
problem, the stable marriage problem and the market clearing price problem. In
this paper, we give the parallel LLP algorithm for many dynamic programming
problems. In particular, we show that the LLP algorithm solves the longest
subsequence problem, the optimal binary search tree problem, and the knapsack
problem. Furthermore, the algorithm can be used to solve the constrained
versions of these problems so long as the constraints are lattice linear. The
parallel LLP algorithm requires only read-write atomicity and no higher-level
atomic instructions.

##  1 Introduction

It has been shown that the Lattice Linear Predicate (LLP) algorithm solves
many combinatorial optimization problems such as the shortest path problem,
the stable marriage problem and the market clearing price problem [1]. In this
paper, we show that many problems that can be solved using dynamic programming
[2] can also be solved in parallel using the LLP algorithm. Dynamic
programming is applicable to problems where it is easy to set up a recurrence
relation such that the solution of the problem can be derived from the
solutions of problems with smaller sizes. One can solve the problem using
recursion; however, recursion may result in many duplicate computations. By
using memoization, we can avoid recomputing previously computed values. We
assume that the problem is solved using dynamic programming with such bottom-
up approach in this paper.

The LLP algorithm views solving a problem as searching for an element in a
finite distributive lattice [3, 4, 5] that satisfies a given predicate $B$.
The predicate is required to be closed under the operation of meet (or,
equivalently lattice-linear, defined in Section 2). For all the problems
considered in the paper, the longest subsequence problem, the optimal binary
search tree problem and the Knapsack problem, the predicate is indeed closed
under meets. Any finite distributive lattice can be equivalently characterized
by a finite poset of its join-irreducibles from Birkhoff’s theorem [3, 4]. The
LLP algorithm works on the finite poset in parallel to find the least element
in the distributive lattice that satisfies the given predicate. It starts with
the bottom element of the lattice and marches towards the top element of the
lattice in a parallel fashion by advancing on any chain of the poset for which
the current element is forbidden.

There are also some key differences between dynamic programming (the bottom-up
approach) and the LLP algorithm. The usual dynamic programming problem seeks a
structure that minimizes (or maximizes) some scalar. For example, the longest
subsequence problem asks for the subsequence in an array $A[1..n]$ that
maximizes the sum. In contrast, the LLP algorithm seeks to minimize or
maximize a vector. In the longest subsequence problem with the LLP approach,
we are interested in the longest subsequence in the array $A[1..i]$ for each
$i\leq n$ that ends at index $i$. Thus, instead of asking for a scalar, we ask
for the vector of size $n$. We get an array $G[1..n]$ and the solution to the
original problem is just the maximum value in the array $G$. Similarly, the
optimal binary search tree problem [6] asks for the construction of an optimal
binary search tree on $n$ symbols such that each symbol $i$ has probability
$p_{i}$ of being searched. Our goal is to find the binary search tree that
minimizes the expected cost of search in the tree. The LLP problem seeks the
optimal binary search tree for all ranges $i\ldots j$ instead of just one
range $1..n$. Finally, the knapsack problem [7, 8] asks for the maximum valued
subset of items that can be fit in a knapsack such that the profit is
maximized and the total weight of the knapsack is at most $W$. The LLP problem
seeks the maximum profit obtained by choosing items from $1..i$ and the total
weight from $1..W$. In all these problems, traditionally we are seeking a
single structure that optimizes a single scalar; whereas the LLP algorithm
asks for a vector. It turns out that that in asking for an optimal vector
instead of an optimal scalar, we do not lose much since the existing solutions
also end up finding the optimal solutions for the subproblems. The LLP
algorithm returns a vector $G$ such that $G[i]$ is optimal for $i$.

The second difference between dynamic programming and the LLP algorithm is in
terms of parallelism. The dynamic programming solution does not explicitly
refers to parallelism in the problem. The LLP algorithm has an explicit notion
of parallelism. The solution uses an array $G$ for all problems and the
algorithm requires the components of $G$ to be advanced whenever they are
found to be forbidden. If $G[i]$ is forbidden for multiple values of $i$, then
$G[i]$ can be advanced for all those values in parallel.

The third difference between dynamic programming and the LLP algorithm is in
terms of synchronization required during parallel execution of the algorithm.
In case of dynamic programming, if the recursive formulas are evaluated in
parallel it is assumed that the values used are correct. In contrast, suppose
that we check for $G[i]$ and $G[j]$ to be forbidden concurrently such that
$G[i]$ ends up using an old value of $G[j]$, the LLP algorithm is still
correct. The only requirement we have for parallelism is that when $G[i]$ uses
a value of $G[j]$, it should either be the most recent value of $G[j]$ or some
prior value. A processor that is responsible for keeping $G[i]$ may get old
value from $G[j]$ in a parallel setting when it gets this value from a cache.
In a message passing system, it may get the old value of $G[j]$ if the message
to update $G[j]$ has not yet arrived at the processor with $G[i]$. Thus, LLP
algorithms are naturally parallel with little synchronization overhead.

The fourth difference between dynamic programming and the LLP algorithm is
that we can use the LLP algorithm to solve a constrained version of the
problem, so long as the constraint itself is lattice-linear. Suppose that we
are interested in the longest subsequence such that successive elements differ
by at least $2$. It can be (easily) shown that this constraint is lattice-
linear. Hence, the LLP algorithm is applicable because we are searching for an
element that satisfies a conjunction of two lattice-linear predicates. Since
the set of lattice-linear predicates is closed under conjunction, the
resulting predicate is also lattice-linear and the LLP algorithm is
applicable. Similarly, the predicate that the symbol $i$ is not a parent of
symbol $j$ is lattice-linear and the constrained optimal binary search tree
algorithm returns the optimal tree that satisfies the given constraint. In the
Knapsack problem, it is easy to solve the problem with the additional
constraint that if the item $x$ is included in the Knapsack, then the item $y$
is also included.

We note here that our goal is not to improve the time or work complexity of
the algorithms, but to provide a single parallel algorithm that solve all of
these problems and their constrained versions. Furthermore, the parallel
algorithm we propose has no synchronization overhead, i.e., they only require
read-write atomicity.

This paper is organized as follows. Section 2 gives background on the LLP
method. Section 3 gives the programming notation used to express LLP
algorithms in the paper. Section 4 applies the LLP method to the longest
subsequence problem. Section 5 give a parallel algorithm for the optimal
binary search tree construction problem. Section 6 gives an LLP algorithm for
the knapsack problem.

##  2 Background

In this section, we cover the background information on the LLP Algorithm [1].
Let ${L}$ be the lattice of all $n$-dimensional vectors of reals greater than
or equal to zero vector and less than or equal to a given vector $T$ where the
order on the vectors is defined by the component-wise natural $\leq$. The
lattice is used to model the search space of the combinatorial optimization
problem. The combinatorial optimization problem is modeled as finding the
minimum element in ${L}$ that satisfies a boolean predicate $B$, where $B$
models feasible (or acceptable solutions). We are interested in parallel
algorithms to solve the combinatorial optimization problem with $n$ processes.
We will assume that the systems maintains as its state the current candidate
vector $G\in{L}$ in the search lattice, where $G[i]$ is maintained at process
$i$. We call $G$, the global state, and $G[i]$, the state of process $i$.

Fig. 1 shows a finite poset corresponding to $n$ processes ($n$ equals two in
the figure), and the corresponding lattice of all eleven global states.

Figure 1: A poset and its corresponding distributive lattice $L$

Finding an element in lattice that satisfies the given predicate $B$, is
called the predicate detection problem. Finding the minimum element that
satisfies $B$ (whenever it exists) is the combinatorial optimization problem.
A key concept in deriving an efficient predicate detection algorithm is that
of a forbidden state. Given a predicate $B$, and a vector $G\in{L}$, a state
$G[j]$ is forbidden (or equivalently, the index $j$ is forbidden) if for any
vector $H\in{L}$ , where $G\leq H$, if $H[j]$ equals $G[j]$, then $B$ is false
for $H$. Formally,

######  Definition 1 (Forbidden State [9])

Given any distributive lattice ${L}$ of $n$-dimensional vectors of
$\mathbf{R}_{\geq 0}$, and a predicate $B$, we define
$\operatorname{forbidden}(G,j,B)\equiv\forall H\in{L}:G\leq
H:(G[j]=H[j])\Rightarrow\neg B(H).$

We define a predicate $B$ to be lattice-linear with respect to a lattice ${L}$
if for any global state $G$, $B$ is false in $G$ implies that $G$ contains a
forbidden state. Formally,

######  Definition 2 (lattice-linear Predicate [9])

A boolean predicate $B$ is lattice-linear with respect to a lattice ${L}$ iff
$\forall G\in{L}:\neg B(G)\Rightarrow(\exists
j:\operatorname{forbidden}(G,j,B))$.

Once we determine $j$ such that $forbidden(G,j,B)$, we also need to determine
how to advance along index $j$. To that end, we extend the definition of
forbidden as follows.

######  Definition 3 ($\alpha$-forbidden)

Let $B$ be any boolean predicate on the lattice ${L}$ of all assignment
vectors. For any $G$, $j$ and positive real $\alpha>G[j]$, we define
$\mbox{forbidden}(G,j,B,\alpha)$ iff

$\forall H\in{L}:H\geq G:(H[j]<\alpha)\Rightarrow\neg B(H).$

Given any lattice-linear predicate $B$, suppose $\neg B(G)$. This means that
$G$ must be advanced on all indices $j$ such that
$\operatorname{forbidden}(G,j,B)$. We use a function $\alpha(G,j,B)$ such that
$\operatorname{forbidden}(G,j,B,\alpha(G,j,B))$ holds whenever
$\operatorname{forbidden}(G,j,B)$ is true. With the notion of $\alpha(G,j,B)$,
we have the Algorithm $LLP$. The algorithm $LLP$ has two inputs — the
predicate $B$ and the top element of the lattice $T$. It returns the least
vector $G$ which is less than or equal to $T$ and satisfies $B$ (if it
exists). Whenever $B$ is not true in the current vector $G$, the algorithm
advances on all forbidden indices $j$ in parallel. This simple parallel
algorithm can be used to solve a large variety of combinatorial optimization
problems by instantiating different $\operatorname{forbidden}(G,j,B)$ and
$\alpha(G,j,B)$.

vector function getLeastFeasible($T$: vector, $B$: predicate)

var $G$: vector of reals initially $\forall i:G[i]=0$;

while $\exists j:\operatorname{forbidden}(G,j,B)$ do

for all $j$ such that $\operatorname{forbidden}(G,j,B)$ in parallel:

if $(\alpha(G,j,B)>T[j])$ then return null;

else $G[j]:=\alpha(G,j,B)$;

endwhile;

return $G$; // the optimal solution

ALGORITHM 1 To find the minimum vector at most $T$ that satisfies $B$

The following Lemma is useful in proving lattice-linearity of predicates.

###### Lemma 1

[1, 9] Let $B$ be any boolean predicate defined on a lattice ${L}$ of vectors.
(a) Let $f:{L}\rightarrow\mathbf{R}_{\geq 0}$ be any monotone function defined
on the lattice ${L}$ of vectors of $\mathbf{R}_{\geq 0}$. Consider the
predicate $B\equiv G[i]\geq f(G)$ for some fixed $i$. Then, $B$ is lattice-
linear.
(b) If $B_{1}$ and $B_{2}$ are lattice-linear then $B_{1}\wedge B_{2}$ is also
lattice-linear.

We now give an example of lattice-linear predicates for scheduling of $n$
jobs. Each job $j$ requires time $t_{j}$ for completion and has a set of
prerequisite jobs, denoted by $pre(j)$, such that it can be started only after
all its prerequisite jobs have been completed. Our goal is to find the minimum
completion time for each job. We let our lattice ${L}$ be the set of all
possible completion times. A completion vector $G\in{L}$ is feasible iff
$B_{jobs}(G)$ holds where $B_{jobs}(G)\equiv\forall j:(G[j]\geq
t_{j})\wedge(\forall i\in pre(j):G[j]\geq G[i]+t_{j})$. $B_{jobs}$ is lattice-
linear because if it is false, then there exists $j$ such that either
$G[j]<t_{j}$ or $\exists i\in pre(j):G[j]<G[i]+t_{j}$. We claim that
$\operatorname{forbidden}(G,j,B_{jobs})$. Indeed, any vector $H\geq G$ cannot
be feasible with $G[j]$ equal to $H[j]$. The minimum of all vectors that
satisfy feasibility corresponds to the minimum completion time.

As an example of a predicate that is not lattice-linear, consider the
predicate $B\equiv\sum_{j}G[j]\geq 1$ defined on the space of two dimensional
vectors. Consider the vector $G$ equal to $(0,0)$. The vector $G$ does not
satisfy $B$. For $B$ to be lattice-linear either the first index or the second
index should be forbidden. However, none of the indices are forbidden in
$(0,0)$. The index $0$ is not forbidden because the vector $H=(0,1)$ is
greater than $G$, has $H[0]$ equal to $G[0]$ but it still satisfies $B$. The
index $1$ is also not forbidden because $H=(1,0)$ is greater than $G$, has
$H[1]$ equal to $G[1]$ but it satisfies $B$.

##  3 Notation

We now go over the notation used in description of our parallel algorithms.
Fig. 2 shows a parallel algorithm for the job-scheduling problems.

The var section gives the variables of the problem. We have a single variable
$G$ in the example shown in Fig. 2. $G$ is an array of objects such that
$G[j]$ is the state of thread $j$ for a parallel program.

The input section gives all the inputs to the problem. These inputs are
constant in the program and do not change during execution.

The init section is used to initialize the state of the program. All the parts
of the program are applicable to all values of $j$. For example, the init
section of the job scheduling program in Fig. 2 specifies that $G[j]$ is
initially $t[j]$. Every thread $j$ would initialize $G[j]$.

The always section defines additional variables which are derived from $G$.
The actual implementation of these variables are left to the system. They can
be viewed as macros. We will show its use later.

The LLP algorithm gives the desirable predicate either by using the forbidden
predicate or ensure predicate. The forbidden predicate has an associated
advance clause that specifies how $G[j]$ must be advanced whenever the
forbidden predicate is true. For many problems, it is more convenient to use
the complement of the forbidden predicate. The ensure section specifies the
desirable predicates of the form $(G[j]\geq expr)$ or $(G[j]\leq expr)$. The
statement ensure $G[j]\geq expr$ simply means that whenever thread $j$ finds
$G[j]$ to be less than $expr$; it can advance $G[j]$ to $expr$. Since $expr$
may refer to $G$, just by setting $G[j]$ equal to $expr$, there is no
guarantee that $G[j]$ continues to be equal to $expr$ — the value of $expr$
may change because of changes in other components. We use ensure statement
whenever $expr$ is a monotonic function of $G$ and therefore the predicate is
lattice-linear.

$P_{j}$: Code for thread $j$ // common declaration for all the programs below
var $G$: array[$1$..$n$] of $0..maxint$;// shared among all threads input:
$t[j]:int$, $pre(j)$: list of $1..n$; init: $G[j]:=t[j]$; job-scheduling:
forbidden: $G[j]<\max\\{G[i]+t[j]~{}|~{}i\in pre(j)\\}$; advance:
$G[j]:=\max\\{G[i]+t[j]~{}|~{}i\in pre(j)\\}$; job-scheduling: ensure:
$G[j]\geq\max\\{G[i]+t[j]~{}|~{}i\in pre(j)\\}$;

Figure 2: LLP Parallel Program for (a) job scheduling problem using forbidden
predicate (b) job scheduling problem using ensure clause

##  4 Longest Increasing Subsequences

We are given an integer array as input. For simplicity, we assume that all
entries are distinct. Our goal is find for each index $i$ the length of the
longest increasing sequence that ends at $i$. For example, suppose the array
$A$ is {35 38 27 45 32}. Then, the desired output is {1 2 1 3 2}. The
corresponding longest increasing subsequences are: (35), (35, 38), (27), (35,
38, 45), (27, 32).

We can define a graph $H$ with indices as vertices. For this example, we have
five vertices numbered $v_{1}$ to $v_{5}$. We draw an edge from $v_{i}$ to
$v_{j}$ if $i$ is less than $j$ and $A[i]$ is also less than $A[j]$. This
graph is clearly acyclic as an edge can only go from a lower index to a higher
index. We use $pre(j)$ to be the set of indices which have an incoming edge to
$j$. The length of the longest increasing subsequence ending at index $j$ is
identical to the length of the longest path ending at $j$.

To solve the problem using LLP, we model it as a search for the smallest
vector $G$ that satisfies the constraint $B\equiv\forall j:G[j]\geq
1\wedge\forall j:G[j]\geq\max\\{G[i]+1~{}|~{}i\in pre(j)\\}$. To understand
$B$, we first consider a stronger predicate $B_{*}=(G[1]=1)\wedge\forall
j:G[j]=\max\\{1,\max\\{G[i]+1~{}|~{}i\in pre(j)\\}\\}$. The interpretation of
$G[j]$ in $B_{*}$ is that it is the length of the longest path that ends in
$j$. Thus, in the longest increasing subsequence problem we are searching for
the vector that satisfies the predicate $B_{*}$. Instead of searching for an
element in the lattice that satisfies $B_{*}$, we search for the least element
in the lattice that satisfies $B$. This allows us to solve for the constrained
version of the problem in which we are searching for an element that satisfies
an additional lattice-linear constraint.

The underlying lattice we consider is that of all vectors of natural numbers
less than or equal to the maximum element in the lattice. A vector in this
lattice is feasible if it satisfies $B$. We first show that the constraint $B$
is lattice-linear.

###### Lemma 2

The constraint $B\equiv(\forall j:G[j]\geq 1)\wedge(\forall
j:G[j]\geq\max\\{G[i]+1~{}|~{}i\in pre(j)\\})$ is lattice-linear.

Proof: Since the predicate $B$ is a conjunction of two predicates, it is
sufficient to show that each of them is lattice-linear from Lemma 1(b). The
first conjunct is lattice linear because the constant function $1$ is
monotone. The second conjunct can be viewed as a conjunction over all $j$. For
a fixed $j$, the predicate $G[j]\geq\max\\{G[i]+1~{}|~{}i\in pre(j)$ is
lattice-linear from Lemma 1(a).

Our goal is to find the smallest vector in the lattice that satisfies $B$.
Now, LLP algorithm can be formulated as 2.

$P_{j}$: Code for thread $j$

input: $A$:array of int;

var $G$: array[$1$ …$n$] of int;

init: $G[j]=1$;

$pre(j):=\\{i\in 1..j-1|A[i]<A[j]\\}$;

ensure: $G[j]\geq\max\\{G[i]+1~{}|~{}i\in pre(j)\\}$;

ALGORITHM 2 Finding the Longest Increasing Subsequence.

This algorithm starts with all values as $1$ and increases the $G$ vector till
it satisfies the constraint $G[j]\geq\max\\{G[i]+1~{}|~{}i\in pre(j)\\}$. The
above algorithm, although correct, does not preclude $G[j]$ from getting
updated multiple times. To ensure that no $G[j]$ is updated more than once, we
introduce a boolean $fixed$ for each index such that we update $G[j]$ only
when it is not fixed and all its predecessors are fixed. With this change, our
algorithm becomes 3.

$P_{j}$: Code for thread $j$

input: $A$:array of int;

var $G$: array[$1$ …$n$] of int;

$fixed$: array[$1$ …$n$] of boolean;

init: $G[j]=1;fixed[j]:=false;$

$pre(j):=\\{i\in 1..j-1|A[i]<A[j]\\}$;

forbidden: $\neg fixed[j]\wedge(\forall i\in pre(j):fixed[i])$;

advance: $G[j]:=\max\\{G[i]+1~{}|~{}i\in pre(j)\\}$;

$fixed[j]:=true$;

ALGORITHM 3 Finding the Longest Increasing Subsequence.

Let us now analyze the complexity of the algorithm. The sequential complexity
is simple because we can maintain the list of all vertices that are forbidden
because all its predecessors are fixed. Once we have processed a vertex, we
never process it again. This is similar to a sequential algorithm of
topological sort. In this case, we examine a vertex exactly once only after
all its predecessors are fixed. The time complexity of this algorithm is
$O(n^{2})$.

For the parallel time complexity, assume that we have $n^{2}$ processors
available. Then, in time $O(\log n)$, one can determine whether the vertex is
forbidden and advance it to the correct value if it is forbidden. This is
because for every $j$, we simply need to check that all vertices in $pre(j)$
are fixed and $j$ is not fixed. By using a parallel reduce operation, we can
check in $O(\log n)$ time whether $j$ is forbidden. If the longest path in the
graph $H$ is $\Delta$, then the algorithm takes $O(\Delta\log n)$ time.

Now, let us consider the situation where each thread $j$ writes the value of
$fixed[j]$ and $G[j]$ without using any synchronization. If any thread $j$
reads the old value of $fixed[i]$ for some $i$ in $pre(j)$, it will not update
$fixed[j]$ at that point. Eventually, it will read the correct value of
$fixed[i]$, and perform $advance$. We do assume in this version that if a
process reads $fixed[i]$ as true, then it reads the correct value of $G[i]$,
because $fixed[i]$ is updated after $G[i]$. Consequently, we get the following
result.

###### Lemma 3

There exists a parallel algorithm for the longest increasing subsequence
problem which uses just read-write atomicity and solves the problem in
$O(\Delta\log n)$ time.

We now add lattice-linear constraints to the problem. Instead of the longest
increasing subsequence, we may be interested in the longest increasing
subsequence that satisfies an additional predicate.

###### Lemma 4

All the following predicates are lattice linear.

  1. 1.

For any $j$, $G[j]$ is greater than or equal to the longest increasing
subsequence of odd integers ending at $j$.

  2. 2.

$G[j]$ is greater than or equal to the longest increasing subsequence such
that $j^{th}$ element in the subsequence exceeds $(j-1)^{th}$ element by at
least $k$.

Proof:

  1. 1.

Since lattice-linear predicates are closed under conjunction, it is sufficient
to focus on a fixed $j$. If $G[j]$ is less than the length of the longest
increasing subsequence of odd integers ending at $j$, then the index $j$ is
forbidden. Unless $j$ is increased the predicate can never become true.

  2. 2.

We view this predicate as redrawing the directed graph $H$ such that we draw
an edge from $v_{i}$ to $v_{j}$ if $i$ is less than $j$ and $A[i]+k$ is less
than or equal to $A[j]$.

We note here that the problem can also be solved in parallel using repeated
squaring of an appropriate matrix. We do not discuss that method here since it
is not work-optimal and generally not efficient in practice.

##  5 Optimal Binary Search Tree

Suppose that we have a fixed set of $n$ symbols called keys with some
associated information called values. Our goal is to build a dictionary based
on binary search tree out of these symbols. The dictionary supports a single
operation search which returns the value associated with the the given key. We
are also given the frequency of each symbol as the argument for the search
query. The cost of any search for a given key is given by the length of the
path from the root of the binary search tree to the node containing that key.
Given any binary search tree, we can compute the total cost of the tree for
all searches. We would like to build the binary search tree with the least
cost.

Let the frequency of key $i$ being searched is $p_{i}$. We assume that the
keys are sorted in increasing order of $p_{i}$. Our algorithm is based on
building progressively bigger binary search trees. The main idea is as
follows. Suppose symbol $k$ is the root of an optimal binary search tree for
symbols in the range $[i..j]$. The root $k$ divides the range into three parts
– the range of indices strictly less than $k$, the index $k$, and the range of
indices strictly greater than $k$. The left or the right range may be empty.
Then, the left subtree and the right subtree must themselves be optimal for
their respective ranges. Let $G[i,j]$ denote the least cost of any binary
search tree built from symbols in the range $i..j$. We use the symbol $s(i,j)$
as the sum of all frequencies from the symbol $i$ to $j$, i.e.,

$s(i,j)=\sum_{k=i}^{j}p_{k}$

For convenience, we let $s(i,j)$ equal to $0$ whenever $i>j$, i.e., the range
is empty.

We now define a lattice linear constraint on $G[i,j]$. Let $i\leq k<j$.
Consider the cost of the optimal tree such that symbol $k$ is at the root. The
cost has three components: the cost of the left subtree if any, the cost of
the search ending at this node itself and the cost of search in the right
subtree. The cost of the left subtree is

$G[i,k-1]+s(i,k-1)$

whenever $i<k$. The cost of the node itself is $s(k,k)$. The cost of the right
subtree is

$G[k+1,j]+s(k+1,j)$

Combining these expressions, we get

$G[i,j]=\min_{i\leq k<j}(G[i,k-1]+s(i,j)+G[k+1,j])$

This is also the least value of $G[i,j]$ such that

$G[i,j]\geq\min_{i\leq k<j}(G[i,k-1]+s(i,j)+G[k+1,j])$

We now show that the above predicate is lattice-linear.

###### Lemma 5

The constraint $B\equiv\forall i,j:G[i,j]\geq\min_{i\leq
k<j}(G[i,k-1]+s(i,j)+G[k+1,j])$ is lattice-linear.

Proof: Suppose that $B$ is false, i.e., $\exists i,j:G[i,j]<\min_{i\leq
k<j}(G[i,k-1]+s(i,j)+G[k+1,j]).$ This means that there exists $i,j,k$ with
$i\leq k<j$ such that $G[i,j]<(G[i,k-1]+s(i,j)+G[k+1,j])$. This means the the
index $(i,j)$ is forbidden and unless $G[i,j]$ is increased, the predicate $B$
can never become true irrespective of how other components of $G$ are
increased.

We now have our LLP-based algorithm for Optimal Binary Search Tree as
Algorithm 4. The program has a single variable $G$. It is initialized so that
$G[i,i]$ equals $p[i]$ and $G[i,j]$ equals zero whenever $i$ is not equal to
$j$. The algorithm advances $G[i,j]$ whenever it is smaller than $\min_{i\leq
k<j}G[i,k-1]+s(i,j)+G[k+1,j]$. In Algorithm 4, we have used the awlways clause
as a macro that uses $s(i,j)$ as a short form for $\sum_{k=i}^{j}p[k]$.

$P_{i,j}$: Code for thread $(i,j)$

input: $p$:array of real;// frequency of each symbol

init: $G[i,j]=0~{}\forall i\neq j$;

$G[i,i]=p[i]$;

always: $s(i,j)=\sum_{k=i}^{j}p[k]$

ensure:

$G[i,j]\geq\min_{i\leq k<j}G[i,k-1]+s(i,j)+G[k+1,j]$

priority: $(j-i)$

ALGORITHM 4 Finding An Optimal Binary Search Tree

Although, the above algorithm will give us correct answers, it is not
efficient as it may update $G[i,j]$ before $G[i,k]$ and $G[k,j]$ for $i\leq
k<j$ have stabilized. However, the following scheduling strategy ensures that
we update $G[i,j]$ at most once. We check for whether $G[i,j]$ is forbidden in
the order of $j-i$. Hence, initially all $G[i,j]$ such that $j=i+1$ are
updated. This is followed by all $G[i,j]$ such that $j=i+2$, and so on. We
capture this scheduling strategy with the ${\bf priority}$ statement. We pick
$G[i,j]$ to update such that $(j-i)$ have minimal values. Of course, our goal
is to compute $G[1,n]$. With the above strategy of updating $G[i,j]$, we get
that $G[i,j]$ is updated at most once. Since there are $O(n^{2})$ possible
values of $G[i,j]$ and each takes $O(n)$ work to update, we get the work
complexity of $O(n^{3})$. On a CREW PRAM, we can compute all $i,j$ with the
fixed difference in parallel. By using $O(\log n)$ span algorithm to compute
$\min$, we get the parallel time complexity as $O(n\log n)$. Thus, we have the
following result.

###### Lemma 6

There exists a parallel algorithm for the optimal binary search tree problem
which uses just read-write atomicity and solves it in $O(n\log n)$ parallel
time.

We now consider the constrained versions of the problem.

###### Lemma 7

All the following predicates are lattice linear.

  1. 1.

Key $x$ is not a parent for any key.

  2. 2.

The difference in the sizes of the left subtree and the right subtree is at
most $1$.

Proof:

  1. 1.

This requirement changes the ensure predicate to $G[i,j]\geq\min_{i\leq
k<j,k\neq x}G[i,k-1]+s(i,j)+G[k+1,j]$. The right hand side of the constraint
continues to be monotonic and therefore it is lattice linear.

  2. 2.

This requirement changes the ensure predicate to $G[i,j]\geq\min_{i\leq
k<j,|k-1-i,j-k-1|\leq 1}G[i,k-1]+s(i,j)+G[k+1,j]$. This change simply
restricts the values of $k$, and the right hand side continues to be
monotonic.

Remark: A problem very similar to the optimal Binary Search tree problem is
that of constructing an optimal way of multiplying a chain of matrices. Since
matrix multiplication is associative, the product of matrices
$(M_{1}*M_{2})*M_{3}$ is equal to $M_{1}*(M_{2}*M_{3})$. However, depending
upon the dimensions of the matrices, the computational effort may be
different. We let the dimension of matrix $M_{i}$ be $m_{i-1}\times m_{i}$.
Note that this keep the matrix product well-defined because the dimension of
matrix $M_{i+1}$ would be $m_{i}\times m_{i+1}$ and the product $M_{i}\times
M_{i+1}$ is well-defined. We can view any evaluation of a chain as a binary
tree where the intermediate notes are the multiplication operation and the
leaves are the matrices themselves. Suppose, our goal is to compute the
optimal binary tree for multiplying matrices in the range $M_{i}\ldots M_{j}$.
Borrowing ideas from the previous section, we let $G[i,j]$ denote the optimal
cost of computing the product of matrices in the range $M_{i}\ldots M_{j}$.
Suppose that this product is broken into products of $M_{i}\ldots M_{k}$ and
$M_{k+1}\ldots M_{j}$ and then multiplication of these two matrices. We can
compute the cost of this tree as

$G[i,k]+G[k+1,j]+m_{i-1}m_{k}m_{j}$

Then, we have the following predicate on $G$.

$G[i,j]\geq\min_{i\leq k<j}(G[i,k]+m_{i-1}m_{k}m_{j}+G[k+1,j]$

The reader will notice the similarity with the optimal binary search tree
problem and this problem and the same algorithm can be adapted to solve this
problem.

##  6 Knapsack Problem

We are given $n$ items with weights $w_{1},w_{2},\ldots,w_{n}$ and values
$v_{1},v_{2},\ldots,v_{n}$. We are also given a knapsack that has a capacity
of $W$. Our goal is to determine the subset of items that can be carried in
the knapsack and that maximizes the total value. The standard dynamic
programming solution is based on memoization of the following dynamic
programming formulation [10, 11]. Let $G[i,w]$ be the maximum value that can
be obtained by picking items from $1..i$ with the capacity constraint of $w$.
Then, $G[i,w]=max(G[i-1,w-w_{i}]+v_{i},G[i-1,w])$. The first argument of the
max function corresponds to the case when the item $i$ is included in the
optimal set from $1..i$, and the second argument corresponds to the case when
the item $i$ is not included and hence the entire capacity can be used for the
items from $1..i-1$. If $w_{i}>w$, then the item $i$ can never be in the
knapsack and can be skipped. The base cases are simple. The value of $G[0,w]$
and $G[i,0]$ is zero for all $w$ and $i$. Our goal is to find $G[n,W]$. By
filling up the two dimensional array $G$ for all values of $0\leq i\leq n$ and
$0\leq w\leq W$, we get an algorithm with time complexity $O(nW)$.

We can model this problem using lattice-linear predicates as follows. We model
the feasibility as $G[i,w]\geq\max(G[i-1,w-w_{i}]+v_{i},G[i-1,w])$ for all
$i,w>0$ and $w_{i}\leq w$. Also, $G[i,w]=0$ if $i=0$ or $w=0$. Our goal is to
find the minimum vector $G$ that satisfies feasibility.

###### Lemma 8

The constraint $B\equiv\forall
i,w:G[i,w]\geq\max(G[i-1,w-w_{i}]+v_{i},G[i-1,w])$ for $w_{i}\leq w$ is
lattice-linear.

Proof: If the predicate $B$ is false, there exists $i$ and $w$ such that
$G[i,w]<\max(G[i-1,w-w_{i}]+v_{i},G[i-1,w])$. The value $G[i,w]$ is forbidden;
unless $G[i,w]$ is increased the predicate can never become true.

$P_{i,j}$: Code for thread $(i,j)$

input: $w,v$:array[$1$..$n$] of int;// weight and value of each item

var: $G$:array[$0\ldots n$, $0\ldots W$] of int;

init: $G[i,j]=0~{}if~{}(i=0)\vee(j=0)$;

ensure:

$G[i,j]\geq\max\\{G[i-1,j-w_{i}]+v_{i},G[i-1,j]\\}$ if $j\geq w_{i}$

$\geq G[i-1,j]$, otherwise.

ALGORITHM 5 Finding An Optimal Solution to the Knapsack Problem

Algorithm 5 updates the value of $G[i,j]$ based only on the values of
$G[i-1,.]$. Furthermore, $G[i,j]$ is always at least $G[i-1,j]$. Based on this
observation, we can simplify the algorithm as follows. We consider the problem
of adding just one item to the knapsack given the constraint that the total
weight does not exceed $W$. We maintain the list of all optimal configurations
for each weight less than $W$.

$P_{j}$: Code for thread $j$

input: $w,v$: int;// weight and value of the next item

$C$: array[$0\ldots W$] of int;

var: $G$:array[$0\ldots W$] of int;

init: $\forall j:G[j]=C[j]$;

ensure:

$G[j]\geq C[j-w]+v$ if $j\geq w$

ALGORITHM 6 Finding An Optimal Solution to the Incremental Knapsack Problem

The incremental algorithm can be implemented in $O(1)$ parallel time using
$O(W)$ processors as shown in Fig. 6. Each processor $j$ can check whether
$G[j]$ needs to be advanced.

We can now invoke the incremental Knapsack algorithm as Algorithm 7. If we had
$W$ cores, then computing $G[i,.]$ from $G[i-1,.]$ can be done in $O(1)$
giving us the span of $O(n)$.

$P_{j}$: Code for thread $j$

input: $w,v$:array[$1$..$n$] of int;// weight and value of each item

var: $G$:array[$0\ldots W$] of int;

init: $\forall j:G[j]=0$;

for $i:=1$ to $n$ do

$G:=IncrKnapsack2(w[i],v[i],G)$;

ALGORITHM 7 Finding An Optimal Solution to the Knapsack Problem

We now add some lattice-linear constraints to the Knapsack problem. In many
applications, some items may be related and the constraint $x_{a}\Rightarrow
x_{b}$ means that if the item $x_{a}$ is included in the Knapsack then the
item $x_{b}$ must also be included. Thus, the item $x_{a}$ has profit of zero
if $x_{b}$ is not included. The item $x_{b}$ has utility even without $x_{a}$
but not vice-versa. Without loss of generality, we assume that all weights are
strictly positive, and that index $b<a$. In the following Lemma, we use an
auxiliary variable $S[i,j]$ that keeps the set of items included in $G[i,j]$
and not just the profit from those items.

###### Lemma 9

First assume that $(i\neq a)$. Let $B(i,w)\equiv
G[i,w]\geq\max(G[i-1,w-w_{i}]+v_{i},G[i-1,w])$ for $(w_{a}\leq w)$ and
$G[i,w]\geq G[i-1,w]$, otherwise. This predicate corresponds to any item $i$
different from $a$. The value with a bag of capacity $w$ is always greater
than or equal to the choice of picking the item or not picking the item.

Let $B(a,w)\equiv G[a,w]\geq\max(G[a-1,w-w_{a}]+v_{a},G[a-1,w])$ if $b\in
S[a-1,w-w_{a}]\wedge(w_{a}\leq w)$ and $G[a,w]\geq G[a-1,w]$, otherwise.

Then, $B(i,w)$ is lattice-linear for all $i$ and $w$.

Proof: Suppose that $B(i,w)$ is false for some $i$ and $w$. Unless $G[i,w]$ is
increased, it can never become true.

##  7 Conclusions

In this paper, we have shown that many dynamic programming problems can be
solved using a single parallel Lattice-Linear Predicate algorithm. In
particular, LLP algorithm solves the problem of the longest increasing
subsequence, the optimal binary search tree and the knapsack problem. In
addition, it solves the constrained versions of these problems. The parallel
algorithms described in the paper works correctly with read-write atomicity of
variables without any use of locks.

## References

  * [1] Vijay K. Garg.  Predicate detection to solve combinatorial optimization problems.  In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 235–245. ACM, 2020.
  * [2] Richard Bellman.  On the theory of dynamic programming.  Proceedings of the National Academy of Sciences of the United States of America, 38(8):716, 1952.
  * [3] G. Birkhoff.  Lattice Theory.  Providence, R.I., 1967.  third edition.
  * [4] B. A. Davey and H. A. Priestley.  Introduction to Lattices and Order.  Cambridge University Press, Cambridge, UK, 1990.
  * [5] Vijay K Garg.  Lattice Theory with Computer Science Applications.  Wiley, New York, NY, 2015.
  * [6] Donald E. Knuth.  Optimum binary search trees.  Acta informatica, 1(1):14–25, 1971.
  * [7] Ellis Horowitz and Sartaj Sahni.  Computing partitions with applications to the knapsack problem.  Journal of the ACM (JACM), 21(2):277–292, 1974.
  * [8] Oscar H Ibarra and Chul E Kim.  Fast approximation algorithms for the knapsack and sum of subset problems.  Journal of the ACM (JACM), 22(4):463–468, 1975.
  * [9] Craig M Chase and Vijay K Garg.  Detection of global predicates: Techniques and their limitations.  Distributed Computing, 11(4):191–201, 1998.
  * [10] Vijay V. Vazirani.  Approximation Algorithms.  Springer-Verlag, Berlin, Germany, 2001.
  * [11] David B Shmoys David P Williamson.  The Design of Approximation Algorithms.  Cambridge University Press, 2010.


# On Operator-valued Semicircular Random Variables

###### Abstract.

In this paper, we discuss some special properties of operator-valued
semicircular random variables including representation of the Cauchy transform
of a compactly supported probability measure in terms of their operator-valued
Cauchy transforms and existence of nonzero discrete part of their associated
distributions.

Mohsen Soltanifar111Mohsen Soltanifar
Department of Mathematics and Statistics, University of Saskatchewan, 106
Wiggins Road, Saskatoon, S7N 5E6, Canada
e-mail<EMAIL_ADDRESS>
Keywords Semicircular distributions, Operator-Valued Non-Commutative
Probability, Cauchy-Stieltjes transform, Continued Fractions

Mathematics Subject Classification (2010). Primary 60B05, 30E20; Secondary
30B70, 47B80

##  1\. Introduction

In his 1995 paper on operator-valued free probability theory, which became one
of the main pillars of free probability , Voiculescu [11] introduced the
operator-valued free central limit theorem and operator-valued semicircular
random variables as operator-valued free analogous of the classical central
limit theorem and normal random variables, respectively. Similar to normal
random variables in classical probability theory, operator-valued semicircular
random variables play key roles in many areas of operator-valued free
probability and related fields. Following Wigner [12] and Voiculescu [10],
Shlyakhtenko showed in [7] that operator-valued semicircular random variables
also play an important role in random matrix theory, as asymptotic
distributional limits of Gaussian band matrices. Later this result found
several applications. We shall mention here the paper of Rashidi Far and
others [6] which shows the importance of matrix-valued semicircular random
variables in communication theory.

This paper deals with exploring some other aspects of operator-valued
semicircular random variables. Our investigation originates from a question of
Speicher on the existence of a discrete part in the spectrum of a matrix-
valued semicircular random variable. Following well-established methods in
noncommutative probability, we approach this problem through the study of
distributions of such a random variable with respect to convenient positive
linear functionals. In our work we were led to question roughly which
probability measures can occur as scalar-valued distributions of operator-
valued semicircular random variables. It turns out that the operator-valued
semicircular random variables have a certain universal property: For given
arbitrary compactly supported probability measure, its associated Cauchy
transform is the composition of an extremal state and the operator-valued
Cauchy transform of an infinite dimensional matrix-valued semicircular random
variable (Theorem 3.1). Moreover, our proof gives a constructive method to
find this semicircular random variable based on the continued fraction
representation of the Cauchy transform of the given probability measure. Our
second result directly concerns the discrete part of the distribution of a
matrix-valued semicircular random variable with respect to the linear
functional induced by the composition of the expectation with the matrix
trace. It was noted by Speicher (private communications with Belinschi) that
an $M_{2}(\mathbb{C})-$valued semicircular random variable with variance
$\eta\left(\begin{array}[]{cc}z&v\\\
y&w\end{array}\right)=\left(\begin{array}[]{cc}0&1\\\
0&0\end{array}\right)\left(\begin{array}[]{cc}z&v\\\
y&w\end{array}\right)\left(\begin{array}[]{cc}0&0\\\ 1&0\end{array}\right)$
has a purely discrete distribution equal to
$\mu=\frac{1}{4}\delta_{+1}+\frac{1}{2}\delta_{0}+\frac{1}{4}\delta_{-1}.$
Motivated by this observation and the proof of the Proposition 3.1, we were
led to show in Theorem 4.1 that any matrix-valued semicircular random variable
with nilpotent variance has an atom at zero. Finally, by combining the methods
used in the proofs of the previous results, it is shown that the semicircular
distributions of finite dimensional matrix-valued semicircular random
variables can cover finitely supported probability measures in a special
sense. This paper is divided into three sections including preliminaries,
representation of the Cauchy transform using semicircular random variables and
a discussion of atoms of distributions of matrix-valued semicircular random
variables.

##  2\. Preliminaries

The reader who has studied the concepts of Cauchy or Cauchy-Stieltjes
transform, continued fraction, operator-valued noncommutative random
variables, and semicircular distributions is well acquainted with the
following definitions and results. For an essential account of the mentioned
concepts, see [4], [8], and [11]. Throughout this paper it is assumed that the
probability measure $\mu$ on $\mathbb{R}$ is compactly supported. We begin
with a definition:

######  Definition 2.1.

Let $\mu$ be a probability measure on the Borel $\sigma$-algebra of
$\mathbb{R}$ . The associated Cauchy transform $G_{\mu}$ to $\mu$ is defined
by:

$G_{\mu}(\xi)=\int_{\mathbb{R}}\frac{d\mu(t)}{\xi-t}\ \ \ \ Im\xi\neq 0.$

Some properties of $G_{\mu}$ are listed in the following proposition. We
denote by $\mathbb{C}^{+}=\\{\xi\in\mathbb{C}:Im\xi>0\\},$
$Supp(\mu)=\mathbb{R}\setminus\bigcup\\{U\subseteq\mathbb{R}|U\
open,\mu(U)=0\\},$ and
$\Gamma_{\alpha}(r)=\\{\xi\in\mathbb{C}^{+}:|Re(\xi)-r|<\alpha Im(\xi)\\}\ \
(-\infty<r<\infty).$

######  Proposition 2.1.

Let $G=G_{\mu}$ be the Cauchy transform of a probability measure $\mu$ on
$\mathbb{R}.$ Then:

(i) $G$ is analytic on $\mathbb{C}\setminus Supp(\mu),$
(ii) If $\xi\in\mathbb{C}^{+}(\mathbb{C}^{-}),$ then
$G(\xi)\in\mathbb{C}^{-}(\mathbb{C}^{+}),$
(iii) $\lim_{\Gamma_{\alpha}(0)\ni\xi\rightarrow\infty}\xi.G(\xi)=1,$ for any
fixed $0<\alpha<\infty.$

Note that any function can be identified as a Cauchy transform of a
probability measure on $\mathbb{R}$ by possessing the three mentioned
properties in the Proposition above [8]. In addition, it is straightforward to
check that:

(1) $\displaystyle\lim_{\Gamma_{\alpha}(r)\ni\xi\rightarrow
r}(\xi-r)G_{\mu}(\xi)$ $\displaystyle=$ $\displaystyle\mu(\\{r\\})\ \
(-\infty<r<\infty).$

######  Definition 2.2.

A probability measure $\mu$ on $\mathbb{R}$ is said to have finite moment of
order $m\geq 1$ if $\int_{\mathbb{R}}|t|^{m}d\mu(t)<\infty,$ and in this case
the $m^{th}$ moment of $\mu$ is defined by
$M_{m}=\int_{\mathbb{R}}t^{m}d\mu(t).$

We denote the set of all Borel probability measures on $\mathbb{R}$ having
finite moments of all orders by $\mathcal{B}_{fm}(\mathbb{R}).$ It is trivial
that any compactly supported probability measure $\mu$ is in this set, and as
a corollary of the Carleman’s moment test [4, Theorem 1.36] it is a solution
of the determinate moment problem. Next, using the idea of associated Gram-
Schmidt orthonormal polynomials to a probability measure $\mu$, one can prove
the existence of the so-called Jacobi coefficients of the given probability
measure $\mu\in\mathcal{B}_{fm}(\mathbb{R}),$ [4, Theorem 1.44]:

######  Theorem 2.3.

Let $\\{p_{m}(t)\\}_{m=0}^{\infty}$ be the Gram-Schmidt orthonormal
polynomials associated with given $\mu\in\mathcal{B}_{fm}(\mathbb{R}).$ Then
there exists a pair of sequences
$\\{\alpha_{m}\\}_{m=1}^{\infty}\subseteq\mathbb{R}$ and
$\\{\omega_{m}\\}_{m=1}^{\infty}\subseteq\mathbb{R}^{+}$ uniquely determined
by:

$\displaystyle p_{0}(t)$ $\displaystyle=$ $\displaystyle 1,$ (2)
$\displaystyle p_{1}(t)$ $\displaystyle=$ $\displaystyle t-\alpha_{1},$
$\displaystyle tp_{m}(t)$ $\displaystyle=$ $\displaystyle
p_{m+1}(t)+\alpha_{m+1}p_{m}(t)+\omega_{m}p_{m-1}(t)\ m\geq 1,$

where in which, if $|Supp(\mu)|=\infty,$ both
$\\{\alpha_{m}\\}_{m=1}^{\infty},\\{\omega_{m}\\}_{m=1}^{\infty}$ are infinite
sequences, and if $|Supp(\mu)|=m_{0}<\infty,$ we have
$\\{\alpha_{m}\\}_{m=1}^{\infty}=\\{\alpha_{m}\\}_{m=1}^{m_{0}}$ and
$\\{\omega_{m}\\}_{m=1}^{\infty}=\\{\omega_{m}\\}_{m=1}^{m_{0}-1}$ with
$p_{m_{0}}=0.$

Note that as a corollary of the equations (2.3), for the compactly supported
probability measure $\mu\in\mathcal{B}_{fm}(\mathbb{R})$ we have:

(3) $\displaystyle\sup_{m}(|\alpha_{m}|+\omega_{m})$ $\displaystyle\leq$
$\displaystyle 2\sup_{t\in Supp(\mu)}|t|<\infty.$

The following theorem gives a continued fraction representation of the
associated Cauchy transform of any probability measure
$\mu\in\mathcal{B}_{fm}(\mathbb{R}),$ [4, Theorem 1.97]:

######  Theorem 2.4.

Let $\mu\in\mathcal{B}_{fm}(\mathbb{R})$ and
$(\\{\omega_{n}\\}_{n=1}^{\infty},\\{\alpha_{n}\\}_{n=1}^{\infty})$ be its
Jacobi coefficients. If $\mu$ is the solution of the determinate moment
problem, then the Cauchy transform of it is expanded into a continued fraction

$G_{\mu}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}}}}}}}\
\ \ \ Im(\xi)\neq 0.$

Before introducing the distribution of operator-valued semicircular random
variables, we remind the following essential definitions and results from the
operator-valued noncommutative probability theory:

######  Definition 2.5.

(1) Let $A$ be a unital $*$-algebra and let $B$ denote a fixed unital
$*$-subalgebra of $A$ over $\mathbb{C}$. A linear map $E_{B}:A\rightarrow B$
is called a conditional expectation if it satisfies the following conditions:

(i) $E_{B}(b_{1}ab_{2})=b_{1}E_{B}(a)b_{2}$ for all $a\in A,\ b_{1},b_{2}\in
B$, and $E_{B}(1)=1,$
(ii) $E_{B}(a^{*}a)\geq 0,$ for all $a\in A,$

(2) A triple $(A,E_{B},B)$ as in part (1) is called a $B$-valued non-
commutative probability space. An element $a\in A$ is called a $B$-valued
random variable,
(3) Let $(A,E_{B},B)$ be as in part (2), and $B\subseteq A_{i}\subseteq A(i\in
I)$ be subalgebras. The family $\\{A_{i}\\}_{i\in I}$ is called free over $B$
if

$E_{B}(a_{i_{1}}a_{i_{2}}\cdots a_{i_{n}})=0$

whenever $i_{1}\neq i_{2},i_{2}\neq i_{3},\cdots,i_{n-1}\neq
i_{n},a_{i_{j}}\in A_{i_{j}}$ and $E_{B}(a_{i_{j}})=0,(1\leq j\leq n).$

We call the family $\\{X_{i}\\}_{i\in I}$ of subsets of A (elements
$\\{a_{i}\\}_{i\in I}$ of A) free if the corresponding family of subalgebras
$\\{\langle X_{i}\cup B\rangle\\}_{i\in I}$ ($\\{\langle\\{a_{i}\\}\cup
B\rangle\\}_{i\in I}$) is free.

Given an operator-valued noncommutative probability space $(A,E_{B},B)$ and a
$B$-valued random variable $a\in A,$ the associated moments of $a$ are, by
definition, the multilinear functionals $\\{m_{n}\\}_{n=0}^{\infty}$ defined
by:

$\displaystyle m_{n}:B^{n}\rightarrow B,$ $\displaystyle
m_{n}(b_{1},b_{2},\cdots,b_{n})=E_{B}(ab_{1}ab_{2}\cdots ab_{n}a),$

in which the quantity $m_{0}=E_{B}(a)\in B$ is called the first moment, the
map $b_{1}\mapsto E_{B}(ab_{1}a)$ is called the second moment, and in general
the map $(b_{1},b_{2},\cdots,b_{n})\mapsto E_{B}(ab_{1}ab_{2}\cdots ab_{n}a)$
is called the $(n+1)^{th}$ moment. Next, let $B$ be a Banach algebra, and
$a,a_{1},\cdots,a_{m},\cdots$ be a sequence of of $B$-valued random variables
in $A$ with associated sequences of moments
$\\{m_{n}\\}_{n=0}^{\infty},\\{m_{n}^{(1)}\\}_{n=0}^{\infty},\cdots,\\{m_{n}^{(m)}\\}_{n=0}^{\infty},\cdots,$
respectively. We say that the sequence $\\{a_{m}\\}_{m=1}^{\infty}$
convergence to $a$ in moments if

$\lim_{m\rightarrow\infty}\|m_{n}^{(m)}(b_{1},b_{2},\cdots,b_{n})-m_{n}(b_{1},b_{2},\cdots,b_{n})\|=0,$

for all $(b_{1},b_{2},\cdots,b_{n})\in B^{n},$ and $n\geq 0.$

Having the same assumptions as above, we recall that any $a\in A$ can be
written as $a=Re(a)+i.Im(a)$ where $Re(a)=\frac{a+a^{*}}{2}$ and
$Im(a)=\frac{a-a^{*}}{2i}$ are self-adjoint elements. We define
$\mathbb{H}^{+}(A)=\\{a\in A|Im(a)>0\\},$ where $Im(a)>0$ means
$Im(a)>\epsilon.1$ for some $\epsilon>0$, and similarly $\mathbb{H}^{+}(B).$
Then the operator-valued Cauchy transform of $a\in A$ is an analytic map
$G_{a}$ defined via:

$\displaystyle G_{a}:\mathbb{H}^{+}(B)\rightarrow\mathbb{H}^{-}(B)$
$\displaystyle G_{a}(b)=E_{B}((b-a)^{-1})$ $\displaystyle\ \ \ \ \ \ \ \
=\sum_{n=0}^{\infty}b^{-1}E_{B}((ab^{-1})^{n})\ \
b\in\mathbb{H}^{+}(B),\|b^{-1}\|<\|a\|^{-1}.$

Next, the operator-valued $R-$transform of $a\in A,$ $R_{a}:B\rightarrow B,$
can be defined by the relation

$bG_{a}(b)=1+R_{a}(G_{a}(b)).G_{a}(b)\ \ (b\in B),$

[11, Theorem 4.9.]. The following central limit theorem for operator-valued
random variables is due to Voiculescu, [11, Theorem 8.4.]:

######  Theorem 2.6.

(Free Central Limit Theorem) Let $B$ be a Banach algebra and
$a_{1},a_{2},\cdots,a_{m},\cdots$ be a sequence of free $B$-valued random
variables in the non-commutative operator valued probability space
$(A,E_{B},B)$such that:

(i)$E_{B}(a_{m})=0,\ (m\in\mathbb{N}),$
(ii) there is a bounded linear map $\eta:B\rightarrow B$ such that

$\lim_{n\rightarrow\infty}\frac{\sum_{m=1}^{n}E_{B}(a_{m}ba_{m})}{n}=\eta(b),\
(b\in B),$

(iii) there are constants $C_{k}\ (k\in\mathbb{N})$ such that

$\sup_{m\in\mathbb{N}}\|E_{B}(a_{m}b_{1}a_{m}\cdots b_{k}a_{m})\|\leq
C_{k}\|b_{1}\|\cdots\|b_{k}\|\ (k\in\mathbb{N}).$

Then the sequence $S_{m}=\frac{\sum_{k=1}^{m}a_{k}}{\sqrt{m}}\
(m\in\mathbb{N})$ converges in moments.

The central limit in the above theorem which we shall denote it by $s$ is
called a $B$-valued semicircular element in the context of operator-valued
noncommutative probability, and, as in classical probability theory it is
uniquely determined by its first two moments. Indeed, its $R-$ transform is of
the form

$R_{s}(b)=D+\eta(b),\ (b\in B)$

where $D=E_{B}(s)\in B$ is a self-adjoint element and $\eta:B\rightarrow B$ is
a completely positive map given by $\eta(b)=E_{B}(sbs)-E_{B}(s)bE_{B}(s)\
(b\in B).$ Furthermore, for any completely positive map $\eta:B\rightarrow B$
there exists a $B-$valued semicircular random variable $s$ such that
$\eta(b)=E_{B}(sbs)-E_{B}(s)bE_{B}(s)\ (b\in B),$ [9, Theorem 4.3.1.].

The following result of Helton, Rashidi Far, and Speicher, shows that any
operator-valued semicircular random variable can be uniquely determined by a
functional equation involving only its first two moments, [3]:

######  Theorem 2.7.

Let $A$ be a unital $C^{*}$-algebra, $B$ a $C^{*}$-subalgebra of $A$, and
$s\in A$ be a self-adjoint $B$-valued semicircular random variable with first
moment $D\in B$ and variance $\eta:B\rightarrow B.$ Then its associated
operator-valued Cauchy transform
$G_{s}:\mathbb{H}^{+}(B)\rightarrow\mathbb{H}^{-}(B)$ is the unique solution
of the functional equation

(4) $\displaystyle b.G_{s}(b)=1+(D+\eta(G_{s}(b))).G_{s}(b),\ \ \
(b\in\mathbb{H}^{+}(B)),$

together with asymptotic condition

(5) $\displaystyle\lim_{b^{-1}\rightarrow 0}b.G_{s}(b)=1.$

Let $A$ be a unital $C^{*}$-algebra, $B$ be a unital $C^{*}$-subalgebra of
$A$, $E_{B}:A\rightarrow B$ be a conditional expectation, and
$G_{a}:\mathbb{H}^{+}(B)\rightarrow\mathbb{H}^{-}(B)$ be the operator-valued
Cauchy transform of the self-adjoint random variable $a\in A.$ Let
$\Phi:B\rightarrow\mathbb{C}$ be a given state on the $C^{*}$-algebra $B$ (In
the case of $B=M_{n}(\mathbb{C})$, for some fixed $n\geq 1,$ we can take
$\Phi=tr_{n},$ the normalized trace.), and define a map
$G\colon\mathbb{C}^{+}\rightarrow\mathbb{C}^{-}$ via:

$G(\xi)=(\Phi\circ G_{a})(\xi.1)\ \ \ \xi\in\mathbb{C}^{+}.$

Referring to the note after the Proposition 2.1, it follows that there is a
probability measure $\mu=\mu_{a}\in\mathcal{B}_{fm}(\mathbb{R})$ on
$\mathbb{R},$ which we call the distribution of $a$, such that:

(6) $\displaystyle
G(\xi)=G_{\mu_{a}}(\xi)=\int_{\mathbb{R}}\frac{d\mu_{a}(t)}{\xi-t}\ \ \
\xi\in\mathbb{C}^{+}.$

Note that the atoms of $\mu_{a}$ are determined via Equation (1).

##  3\. Representation of the Cauchy Transform Using Semicircular Random
Variables

The proof of the following results are based on the Theorem 2.7 of Section 2.
Indeed, for given $D$ and $\eta$ as in that theorem, we shall verify the
conditions (4) and (5) for $b=\xi.1\ \ \xi\in\mathbb{C}^{+}$ and $G_{s}(b)$ a
diagonal matrix of complex analytic functions. Then, Theorem 2.7 of Section 2
will guarantee us that there is a semicircular random variable $s$ with first
moment $D$ and variance $\eta$ so that $G_{s}(b)$ is the restriction of the
operator-valued Cauchy transform of $s$ to $\mathbb{C}^{+}.1.$ Next, our
variances $\eta$ will be explicitly constructed as $\eta(b)=v^{*}bv$, [5,
Theorem 4.1.] with $v$ obtained from the Jacobi coefficients of the given
compactly supported probability measure.

The first result deals with the finite dimensional matrix-valued
representations of the Cauchy transform. Here, we consider $\ell_{2}^{n}$ as
$\mathbb{C}^{n}$ with its canonical orthonormal basis $\\{e_{k}\\}_{k=1}^{n}.$

######  Proposition 3.1.

Let $\mu$ be a probability measure with compact support in $\mathbb{R}.$ Then
there exist two sequences $s_{n}^{(1)}$ and $s_{n}^{(2)}\ (n\geq 1)$of self-
adjoint operator valued semicircular random variables with associated
operator-valued Cauchy transforms
$G_{s_{n}^{(1)}}:\mathbb{H}^{+}(M_{n}(\mathbb{C}))\rightarrow\mathbb{H}^{-}(M_{n}(\mathbb{C}))$
and
$G_{s_{n}^{(2)}}:\mathbb{H}^{+}(M_{n}(\mathbb{C}))\rightarrow\mathbb{H}^{-}(M_{n}(\mathbb{C}))\
(n\geq 1)$ such that the Cauchy transform
$G_{\mu}:\mathbb{C}^{+}\rightarrow\mathbb{C}^{-}$ is represented as:

(7) $\displaystyle G_{\mu}(\xi)=\lim_{n\rightarrow\infty}\langle
G_{s_{n}^{(1)}}(\xi.1_{n})e_{1},e_{1}\rangle_{\ell_{2}^{n}}\ \
\xi\in\mathbb{C}^{+},$

and

(8) $\displaystyle G_{\mu}(\xi)=\lim_{n\rightarrow\infty}\langle
G_{s_{n}^{(2)}}(\xi.1_{n})e_{n},e_{n}\rangle_{\ell_{2}^{n}}\ \
\xi\in\mathbb{C}^{+}.$

###### Proof.

Let

$G_{\mu}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}-\displaystyle{\frac{\omega_{n-1}}{\xi-\alpha_{n}-\displaystyle{\frac{\omega_{n}}{\xi-\alpha_{n+1}-}}_{\displaystyle{\ddots}}}}}}}}}}$

be the continued fraction representation of $G_{\mu}$ as in Theorem 2.4. To
prove Equation (7), fix positive integer $n\geq 1,$ then define $b=\xi.1_{n},$
$D_{n}^{(1)}=(\alpha_{k}\delta_{kl})_{k,l=1}^{n}$ and the completely positive
map $\eta_{n}^{(1)}$ via :

$\displaystyle\eta_{n}^{(1)}:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$
$\displaystyle\eta_{n}^{(1)}\big{(}(a_{kl})_{k,l=1}^{n}\big{)}=(\omega_{k}^{\frac{1}{2}}\delta_{(k+1)l})_{k,l=1}^{n}(a_{kl})_{k,l=1}^{n}(\omega_{k-1}^{\frac{1}{2}}\delta_{k(l+1)})_{k,l=1}^{n}.$

Then, for the self-adjoint semicircular element $s_{n}^{(1)}$ with operator-
valued Cauchy transform $G_{s_{n}^{(1)}}$ satisfying the functional equation
(4) of the form:

$bG_{s_{n}^{(1)}}(b)=1+(D_{n}^{(1)}+\eta_{n}^{(1)}(G_{s_{n}^{(1)}}(b)))G_{s_{n}^{(1)}}(b),$

we have $G_{s_{n}^{(1)}}(b)=(g_{n,n-k+1}(\xi)\delta_{kl})_{k,l=1}^{n}$ where :

$g_{n,n-k+1}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}-\displaystyle{\frac{\omega_{n-k+1}}{\xi-\alpha_{n-k+1}}}}}}}}}\
\ 1\leq k\leq n,\ \xi\in\mathbb{C}^{+},$

which can be identified as $(n-k+1)^{th}$ convergent of $G_{\mu}.$
Accordingly:

$\displaystyle
G_{\mu}(\xi)=\lim_{n\rightarrow\infty}g_{n,n}(\xi)=\lim_{n\rightarrow\infty}\langle
G_{s_{n}^{(1)}}(\xi.1_{n})e_{1},e_{1}\rangle_{\ell_{2}^{n}}\ \
\xi\in\mathbb{C}^{+}.$

The proof of Equation (8) is analogous by considering a fixed positive integer
$n\geq 1,$ then defining $b=\xi.1_{n},$
$D_{n}^{(2)}=(\alpha_{n+1-k}\delta_{kl})_{k,l=1}^{n}$ and the completely
positive map $\eta_{n}^{(2)}$ via :

$\displaystyle\eta_{n}^{(2)}:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$
$\displaystyle\eta_{n}^{(2)}\big{(}(a_{kl})_{k,l=1}^{n}\big{)}=(\omega_{n-k+1}^{\frac{1}{2}}\delta_{k(l+1)})_{k,l=1}^{n}(a_{kl})_{k,l=1}^{n}(\omega_{n-k}^{\frac{1}{2}}\delta_{(k+1)l})_{k,l=1}^{n}.$

∎

The following theorem deals with the infinite dimensional matrix valued
representation of the Cauchy transform. Here, we denote by
$B(\ell_{2}(\mathbb{N}))$ the space of bounded operators on the separable
Hilbert space $\ell_{2}(\mathbb{N}),$ and we consider the orthonormal basis
$\\{e_{n}\\}_{n=1}^{\infty}$ of $\ell_{2}(\mathbb{N})$ given by
$e_{n}=\\{\delta_{mn}\\}_{m=1}^{\infty}\ (n\geq 1).$

######  Theorem 3.1.

Let $\mu$ be a compactly supported probability measure in $\mathbb{R}$ with
Jacobi coefficients
$(\\{\omega_{n}\\}_{n=1}^{\infty},\\{\alpha_{n}\\}_{n=1}^{\infty})$. Then
there exist a self-adjoint $B(\ell_{2}(\mathbb{N}))-$valued semicircular
random variable $s$ with first moment
$D=(\alpha_{k}\delta_{kl})_{k,l=1}^{\infty}\in B(\ell_{2}(\mathbb{N})),$ and
variance

$\displaystyle\eta:B(\ell_{2}(\mathbb{N}))\rightarrow B(\ell_{2}(\mathbb{N}))$
$\displaystyle\eta((a_{kl})_{k,l=1}^{\infty})=(\omega_{k}^{\frac{1}{2}}\delta_{(k+1)l})_{k,l=1}^{\infty}(a_{kl})_{k,l=1}^{\infty}(\omega_{k-1}^{\frac{1}{2}}\delta_{k(l+1)})_{k,l=1}^{\infty},$

and an state $\rho:B(\ell_{2}(\mathbb{N}))\rightarrow\mathbb{C}$ such that the
Cauchy transform $G_{\mu}:\mathbb{C}^{+}\rightarrow\mathbb{C}^{-}$ is
represented as:

$G_{\mu}(\xi)=(\rho\circ G_{s})(\xi.1)\ \ \xi\in\mathbb{C}^{+}.$

###### Proof.

Let

$G_{\mu}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}-\displaystyle{\frac{\omega_{n-1}}{\xi-\alpha_{n}-\displaystyle{\frac{\omega_{n}}{\xi-\alpha_{n+1}-}}_{\displaystyle{\ddots}}}}}}}}}}$

be the continued fraction representation of $G_{\mu}$ as in Theorem 2.4 and
consider given $D$ and $\eta$ where using inequality (3) both of them are
bounded in their corresponding norms. Now, as in proof of Proposition 3.1, we
observe that the diagonal matrix

$G_{s}(b)=(x_{kl}\delta_{kl})_{k,l=1}^{\infty},\ \ \ b=\xi.1\in
B(\ell_{2}(\mathbb{N}))$

with entries $x_{nn}$ of the form

$x_{nn}=\frac{1}{\xi-\alpha_{n}-\displaystyle{\frac{\omega_{n}}{\xi-\alpha_{n+1}-\displaystyle{\frac{\omega_{n+1}}{{\xi-\alpha_{n+2}}-\displaystyle{\frac{\omega_{n+2}}{\xi-\alpha_{n+3}-\displaystyle{\frac{\omega_{n+3}}{\xi-\alpha_{n+4}-}}_{\displaystyle{\ddots}}}}}}}}}\
n\geq 1,$

satisfies the equation (4) with condition (5). Consequently, for the state
$\rho:B(\ell_{2}(\mathbb{N}))\rightarrow\mathbb{C}$ defined by:

$\rho(T)=\langle T(e_{1}),e_{1}\rangle_{\ell_{2}(\mathbb{N})}$

the assertion follows. ∎

##  4\. Atoms of Distributions of Matrix-Valued Semicircular Random Variables

In this section, the existence of atoms of distributions of finite dimensional
matrix-valued semicircular random variables is discussed. First of all, we
give a sufficient condition on the variance of a centered semicircular random
variable so that its associated probability measure has atom.

######  Theorem 4.1.

Let
$G_{s}:\mathbb{H}^{+}(M_{n}(\mathbb{C}))\rightarrow\mathbb{H}^{-}(M_{n}(\mathbb{C}))$
be the operator valued Cauchy transform of a $M_{n}(\mathbb{C})$-valued
semicircular random variable $s$ satisfying the functional equation (4),
$b\in\mathbb{H}^{+}(M_{n}(\mathbb{C})),$ where $D=0$ and
$\eta:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$ is a nilpotent
completely positive map. Then the associated probability measure $\mu_{s}$ to
$G_{s}$ has at least one atom .

###### Proof.

Let $\eta,\cdots,\eta^{m-1}\neq 0$ and $\eta^{m}=0,$ for some $m\geq 1.$
Writing the functional equation in the form of
$b-{G_{s}(b)}^{-1}=\eta(G_{s}(b))$ for $\|b^{-1}\|<<\infty$ it follows that:

$\eta^{m-1}(b-{G_{s}(b)}^{-1})=\eta^{m}(G_{s}(b))=0\hskip 28.45274ptIm(b)>0,\
\ \|b^{-1}\|<<\infty.$

Now, if $\ker(\eta^{m-1})=\LARGE 0,$ then $G_{s}(b)=b^{-1}$ and using
Equations (1) and (6) it follows that

$\mu_{s}(\\{0\\})=1,$

proving the assertion. Hence, we may assume $\ker(\eta^{m-1})\neq\LARGE 0.$
Pick $0\neq c\in\ker(\eta^{m-1})\cap M_{n}^{+}(\mathbb{C})$ with $\|c\|=1.$
Then by Schwarz inequality for completely positive maps [5, p. 40], it follows
that:

$\eta^{m-1}(c^{\frac{1}{2^{n}}})^{*}\eta^{m-1}(c^{\frac{1}{2^{n}}})\leq\|\eta^{m-1}(1)\|\eta^{m-1}(c^{\frac{1}{2^{n-1}}})\hskip
28.45274ptn\geq 1,$

and by induction we conclude that $\eta^{m-1}(c^{\frac{1}{2^{n}}})=0\ (n\geq
1).$ By defining:

$p:=^{s.o.t}\lim_{n\rightarrow\infty}c^{\frac{1}{2^{n}}},$

it follows that $p$ is a projection in $\ker(\eta^{m-1}).$

Claim (1): There exists a unique projection $1\neq q\in\ker(\eta^{m-1})$ such
that for any projection $p\in\ker(\eta^{m-1})$ we have: $p\leq q.$

We showed that there is at least one projection $p$ in $\ker(\eta^{m-1}).$ Let
$p_{1},p_{2}$ be two projections in $\ker(\eta^{m-1}).$ Then :

$\eta^{m-1}((p_{1}+p_{2})^{\frac{1}{2^{n}}})^{*}\eta^{m-1}({(p_{1}+p_{2})}^{\frac{1}{2^{n}}})\leq\|\eta^{m-1}(1)\|\eta^{m-1}((p_{1}+p_{2})^{\frac{1}{2^{n-1}}})\
\ n\geq 1,$

and by induction it follows that
$\eta^{m-1}((p_{1}+p_{2})^{\frac{1}{2^{n}}})=0\ (n\geq 1).$ Now, define
$p_{3}:=^{s.o.t}\lim_{n\rightarrow\infty}(p_{1}+p_{2})^{\frac{1}{2^{n}}},$
then $p_{3}$ is a projection in $\ker(\eta^{m-1}).$ On the other hand

$(p_{1}+p_{2})^{\frac{1}{2^{n}}}\geq p_{1},p_{2}\ \ \ (n\geq 1),$

yielding $p_{3}\geq p_{1},p_{2}.$ Next, using the maximality argument and by
repeating this process there will be a unique maximal projection $q$ in
$\ker(\eta^{m-1})$ such that for any other projection $p$ in it, we have
$p\leq q.$ Finally, if $q=1,$ then using the same Schwarz inequality as above,
and the canonical decomposition of elements of $M_{n}(\mathbb{C})$ into its
positive elements it follows that $\eta^{m-1}=0,$ in contradiction to our
hypothesis.

Claim(2): For any $0\neq c\in\ker(\eta^{m-1})\cap M_{n}^{+}(\mathbb{C}),$ we
have $cq=qc=c.$

Indeed, since $c\in M_{n}^{+}(\mathbb{C}),$ by spectral theorem we have:

$c=\sum_{k=1}^{N}\lambda_{k}p_{k}$

where the projections $p_{k}$’s satisfy $\sum_{k=1}^{N}p_{k}=1,\ \
p_{k_{1}}p_{k_{2}}=0\ (1\leq k_{1}\neq k_{2}\leq N)$ and $\lambda_{k}\geq 0\
(1\leq k\leq N).$ Now, define:

$r:=^{s.o.t}\lim_{n\rightarrow\infty}c^{\frac{1}{2^{n}}}.$

Then it follows that $r=\sum_{\lambda_{k}\neq 0}p_{k},$ yielding $p_{k}\leq r\
(\lambda_{k}\neq 0).$ On the other hand, by definition of $q$ we have $r\leq
q$ and hence $p_{k}\leq q\ (\lambda_{k}\neq 0).$ But all of $p_{k}\leq q\
(\lambda_{k}\neq 0),$ and $q$ are projections and, consequently,
$p_{k}q=qp_{k}=p_{k}\ (\lambda_{k}\neq 0).$ Now, by multiplying all sides by
$\lambda_{k}\ (1\leq k\leq N),$ and taking summation the claim is proved.

Next, take $c_{0}=\frac{1}{i}({G_{s}(b)}^{-1}-b)$ where $b=iy.1\ (y>0).$ Then
using the fact that $s$ is centered, $E_{B}(s^{2m-1})=0\ \ m\geq 1,$ by

$\displaystyle Re(G_{s}(b))$ $\displaystyle=$ $\displaystyle
Re\Big{(}\sum_{m=0}^{\infty}b^{-1}E_{B}((sb^{-1})^{m})\Big{)}=Re\Big{(}\sum_{m=0}^{\infty}i^{m+1}(-y)^{m+1}E_{B}(s^{m})\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{m=1}^{\infty}(-y^{2})^{m}E_{B}(s^{2m-1})=0,\ \ \ y>\|s\|$

it follows that

${G_{s}(b)}^{-1}-b=\Big{(}Re(G_{s}(b))+i.Im(G_{s}(b))\Big{)}^{-1}-b=i.\Big{(}-{Im(G_{s}(b))}^{-1}-\frac{b}{i}\Big{)},$

and, hence $c_{0}=\frac{1}{i}({G_{s}(b)}^{-1}-b)=Im(({G_{s}(b)}^{-1}-b))\geq
0.$ Now, by claim (2) for $c=c_{0}$ we have that:

$G_{s}(b)(1-q)=b^{-1}(1-q)=(1-q)G_{s}(b)\ \ \textrm{and}\ \
G_{s}(b)q=qG_{s}(b),$

and hence:

$\displaystyle G_{s}(b)$ $\displaystyle=$
$\displaystyle(1-q)G_{s}(b)(1-q)+qG_{s}(b)q$ $\displaystyle=$ $\displaystyle
b^{-1}(1-q)+qG_{s}(b)q\hskip 28.45274ptb=iy.1\ (y>0),\|b^{-1}\|<<\infty.$

Now, applying analytic continution for the complex function $tr_{n}\circ
G_{s}|_{\mathbb{C}^{+}.1}:\mathbb{C}^{+}\rightarrow\mathbb{C}^{-}$ we conclude
that:

$(tr_{n}\circ G_{s})(\xi.1)=tr_{n}(\xi^{-1}(1-q)+qG_{s}(\xi.1)q)\ \ \
\xi\in\mathbb{C}^{+},$

and, consequently, by another application of the Equations (1) and (6):

$\mu_{s}(\\{0\\})=tr_{n}(1-q)>0,$

completing the proof. ∎

Before stating a more concrete and special case of the above theorem, using M.
D. Choi’s representation of a completely positive map from a matrix algebra to
another matrix algebra [1], we have:

######  Lemma 4.2.

Let $\eta$ be a completely positive map defined by

$\displaystyle\eta:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$
$\displaystyle\eta(a)=\sum_{j=1}^{n^{2}}a_{j}aa_{j}^{*},\ \ a_{j}\in
M_{n}(\mathbb{C})\ (1\leq j\leq n^{2}).$

Then:

(i) if the map $\eta$ is nilpotent, then all matrices $a_{j}\ (1\leq j\leq
n^{2})$ are nilpotent,
(ii) if all matrices $a_{j}\ (1\leq j\leq n^{2})$ are nilpotent and commute
with each other, then the map $\eta$ is nilpotent.

###### Proof.

(i) Let $\eta^{m}=0$ for some $m\geq 1.$ Then, it follows that:

$\displaystyle\sum_{1\leq j_{1},\cdots,j_{m}\leq n^{2}}(a_{j_{1}}\cdots
a_{j_{m}}a)(a_{j_{1}}\cdots a_{j_{m}}a)^{*}$ $\displaystyle=$
$\displaystyle\sum_{1\leq j_{1},\cdots,j_{m}\leq n^{2}}(a_{j_{1}}\cdots
a_{j_{m}})aa^{*}(a_{j_{m}}^{*}\cdots a_{j_{1}}^{*})$ $\displaystyle=$
$\displaystyle\sum_{j_{1}=1}^{n^{2}}\cdots\sum_{j_{m}=1}^{n^{2}}(a_{j_{1}}\cdots
a_{j_{m}})aa^{*}(a_{j_{m}}^{*}\cdots a_{j_{1}}^{*})$ $\displaystyle=$
$\displaystyle\sum_{j_{1}=1}^{n^{2}}a_{j_{1}}\Big{(}\cdots\Big{(}\sum_{j_{m}=1}^{n^{2}}a_{j_{m}}aa^{*}a_{j_{m}}^{*}\Big{)}\cdots\Big{)}a_{j_{1}}^{*}$
$\displaystyle=$ $\displaystyle\eta^{m}(aa^{*})$ $\displaystyle=$
$\displaystyle 0$

for all $a\in M_{n}(\mathbb{C}).$ Consequently, by positivity of all elements
of the form $(a_{j_{1}}\cdots a_{j_{m}}a)(a_{j_{1}}\cdots a_{j_{m}}a)^{*}$ it
follows that

$(a_{j_{1}}\cdots a_{j_{m}}a)(a_{j_{1}}\cdots a_{j_{m}}a)^{*}=0\ \ (1\leq
j_{1},\cdots,j_{m}\leq n^{2}),$

for all $a\in M_{n}(\mathbb{C}).$ On the other hand , $M_{n}(\mathbb{C})$ is a
$C^{*}$-algebra and hence:

$a_{j_{1}}\cdots a_{j_{m}}a=0\ \ (1\leq j_{1},\cdots,j_{m}\leq n^{2}),$

for all $a\in M_{n}(\mathbb{C}),$ or equivalently:

$a_{j_{1}}\cdots a_{j_{m}}=0\ \ (1\leq j_{1},\cdots,j_{m}\leq n^{2}).$

Now, take $j_{1}=\cdots=j_{m}=j$ where $1\leq j\leq n^{2}$ and the desired
result is proved.

(ii) Since $a_{j}\ \ (1\leq j\leq n^{2})$ are nilpotent, it follows that
$a_{j}^{n}=0\ \ (1\leq j\leq n^{2}).$ Put $m=n^{3},$ then by commutativity of
the these matrices it follows that:

$\displaystyle a_{j_{1}}\cdots a_{j_{m}}$ $\displaystyle=$
$\displaystyle\prod_{p=0}^{n-1}\prod_{q=1}^{n^{2}}a_{j_{pn^{2}+q}}=a_{j_{(j_{1},\cdots,j_{m})}}^{n}\prod\prod_{j_{pn^{2}+q}\neq
j_{(j_{1},\cdots,j_{m})}}a_{j_{pn^{2}+q}}=0,$

for all $1\leq j_{1},\cdots,j_{m}\leq n^{2}$. Consequently,

$\displaystyle\eta^{m}(a)$ $\displaystyle=$ $\displaystyle\sum_{1\leq
j_{1},\cdots,j_{m}\leq n^{2}}(a_{j_{1}}\cdots a_{j_{m}})a(a_{j_{m}}^{*}\cdots
a_{j_{1}}^{*})=0$

for all $a\in M_{n}(\mathbb{C}).$ ∎

Considering above lemma, for a category of nilpotent $\eta^{\prime}s$ we have:

######  Corollary 4.3.

Let
$G_{s}:\mathbb{H}^{+}(M_{n}(\mathbb{C}))\rightarrow\mathbb{H}^{-}(M_{n}(\mathbb{C}))$
be the operator-valued Cauchy transform of a $M_{n}(\mathbb{C})$-valued
semicircular random variable $s$ satisfying the functional equation (4),
$b\in\mathbb{H}^{+}(M_{n}(\mathbb{C})),$ $D=0$ and the completely positive map
$\eta$ is given by:

$\displaystyle\eta:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$
$\displaystyle\eta(a)=\sum_{j=1}^{n^{2}}a_{j}aa_{j}^{*},\ \ a_{j}^{n}=0\
(1\leq j\leq n^{2}),\ \ a_{j_{1}}a_{j_{2}}=a_{j_{2}}a_{j_{1}}\ (1\leq
j_{1},j_{2}\leq n^{2}).$

Then the associated probability measure $\mu_{s}$ to $G_{s}$ has at least one
atom at $x=0.$

A few examples of interest are discussed in connection to the Theorem 4.1. :

######  Remarks 4.4.

(i) The converse of the assertion of the Theorem 4.1. does not hold. To see
this, let $n=2$, $0\neq|\alpha|\neq|\beta|\neq 0$ and define:

$a_{1}=\left(\begin{array}[]{cc}0&\alpha\\\ \beta&0\end{array}\right),\ \
a_{j}=0\ (2\leq j\leq 4).$

Under these conditions, considering $D=0$ and $\eta(a)=a_{1}aa_{1}^{*}$ in the
Equation (4) with the restriction condition (5), and solving it for $G_{s}(b)$
yields:

$tr_{2}(G_{s}(b))=\frac{(|\alpha|^{2}+|\beta|^{2})\Big{(}\xi^{2}+\sqrt{(-|\alpha|^{2}+|\beta|^{2}-\xi^{2})^{2}-4.|\alpha|^{2}\xi^{2}}\Big{)}-(|\alpha|^{2}-|\beta|^{2})^{2}}{4\xi|\alpha|^{2}|\beta|^{2}},$

and, by considering the Equations (1) and (6) it follows that:

$\mu_{s}(\\{r\\})=0\ \ \textrm{if}\ \ \ r\neq 0,\
\frac{1}{2}\Big{(}1-\left|\frac{\beta}{\alpha}\right|^{2sgn(1-|\frac{\beta}{\alpha}|)}\Big{)}\
\ \ \textrm{if}\ \ r=0.$

(ii) If the assumption of nilpotency of the map $\eta$ is violated in the
statement of the Theorem 4.1, then the associated distribution can have no
atom. To see this, let $n=2$, $|\alpha|=|\beta|\neq 0$ and define:

$a_{1}=\left(\begin{array}[]{cc}0&\alpha\\\ \beta&0\end{array}\right),\ \
a_{j}=0\ (2\leq j\leq 4).$

Under these conditions, considering $D=0$ and $\eta(a)=a_{1}aa_{1}^{*}$ in the
Equation (4) with the restriction condition (5), and solving it for $G_{s}(b)$
yields:

$tr_{2}(G_{s}(b))=\frac{\xi-\sqrt{\xi^{2}-4|\alpha|^{2}}}{2|\alpha|^{2}}$

Now, by considering the Equation (6), it follows that this is the Cauchy
transform of the standard semicircular law of Wigner which has no atom.

(iii) In the Theorem 4.1 , for given nilpotent map $\eta$ the associated
probability measure to the operator-valued Cauchy transform $G_{s}(b)$ may not
be purely atomic. To see this, let $n=3$ and define :

$a_{1}=\left(\begin{array}[]{ccc}0&1&1\\\ 0&0&1\\\ 0&0&0\end{array}\right),\ \
a_{j}=0\ (3\leq j\leq 9).$

Under these conditions, considering $D=0$ and $\eta(a)=a_{1}aa_{1}^{*}$ in the
Equation (4) with the restriction condition (5), and solving it for $G_{s}(b)$
with the Groebner basis method [2] in Mathematica, it follows that:

$tr_{3}(G_{s}(b))=\frac{1}{3}\Big{(}\frac{1}{\xi}+\frac{\xi-\sqrt{\xi^{2}-4}}{2}+(\xi^{2}-1)\big{(}\frac{\xi-\sqrt{\xi^{2}-4}}{2}\big{)}^{3}\Big{)},$

and, by considering the Equations (1) and (6) it follows that:

$\mu_{s}(\\{r\\})=0\ \ \textrm{if}\ \ r\neq 0,\ \frac{1}{3}\ \textrm{if}\ \
r=0,$

showing that $\mu_{s}$ is not purely atomic.

We end this section by mentioning a “covering property” of distributions of
matrix-valued semicircular random variables. Before that, we need a
definition:

######  Definition 4.5.

Let $\mu$ and $\nu$ be two probability measures on $\mathbb{R}$. We shall say
that $\nu$ is a component of $\mu$ if there exists a finite family
$\\{\nu_{1},\dots,\nu_{n}\\}$ of probability measures so that
$\nu\in\\{\nu_{1},\dots,\nu_{n}\\}$ and

$\mu=\sum_{j=1}^{n}\alpha_{j}\nu_{j}$

for some $\alpha_{1},\dots,\alpha_{n}\in[0,1]$ satisfying
$\alpha_{1}+\cdots+\alpha_{n}=1$.

######  Proposition 4.1.

Any probability measure $\mu$ on $\mathbb{R}$ whose support is a finite set
can be realized as a component of a semicircular distribution $\mu_{s}$ of
some matrix-valued semicircular random variable $s$ with nilpotent variance.

###### Proof.

Assume $|Supp(\mu)|=n<\infty$, and let

$G_{\mu}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}\displaystyle{\frac{\omega_{n-1}}{\xi-\alpha_{n}}}}}}}}}$

be the continued fraction representation of $G_{\mu}$ as in Theorem 2.4. Then
as in the proof of the Proposition 3.1, define $b=\xi.1_{n},\
D_{n}=(\alpha_{k}\delta_{kl})_{k,l=1}^{n}$ and the nilpotent completely
positive map $\eta_{n}$ via:

$\displaystyle\eta_{n}:M_{n}(\mathbb{C})\rightarrow M_{n}(\mathbb{C})$
$\displaystyle\eta_{n}\big{(}(a_{kl})_{k,l=1}^{n}\big{)}=(\omega_{k}^{\frac{1}{2}}\delta_{(k+1)l})_{k,l=1}^{n}(a_{kl})_{k,l=1}^{n}(\omega_{k-1}^{\frac{1}{2}}\delta_{k(l+1)})_{k,l=1}^{n}.$

Then for the self-adjoint semicircular element $s=s_{n}$ with operator-valued
Cauchy transform $G_{s}$ satisfying the functional equation (4) in the form:

$bG_{s}(b)=1+(D_{n}+\eta_{n}(G_{s}(b)))G_{s}(b),$

we have

$G_{\mu}(\xi)=\langle G_{s}(\xi.1_{n})e_{1},e_{1}\rangle_{\ell_{2}^{n}}\ \ \
\xi\in\mathbb{C}^{+}.$

Next, let $\mu_{k}\ \ (1\leq k\leq n)$ be a finitely supported probability
measure on $\mathbb{R}$ with associated Cauchy transform:

$G_{\mu_{n-(k-1)}}(\xi)=\frac{1}{\xi-\alpha_{1}-\displaystyle{\frac{\omega_{1}}{\xi-\alpha_{2}-\displaystyle{\frac{\omega_{2}}{{\xi-\alpha_{3}-}_{\displaystyle{\ddots}\displaystyle{\frac{\omega_{k-1}}{\xi-\alpha_{k}}}}}}}}}\
\ (1\leq k\leq n).$

Note that $\mu=\mu_{1}.$ Then by proof of the Proposition 3.1, we have

(9) $\displaystyle G_{\mu_{k}}(\xi)=\langle
G_{s}(\xi.1_{n})e_{k},e_{k}\rangle_{\ell_{2}^{n}}\ \ \ (1\leq k\leq n),\
\xi\in\mathbb{C}^{+}.$

Consequently, by Equations (6) and (9), we have:

$G_{\mu_{s}}(\xi)=tr_{n}(G_{s}(\xi.1))=\frac{1}{n}\sum_{k=1}^{n}\langle
G_{s}(\xi.1)e_{k},e_{k}\rangle_{\ell_{2}^{n}}=\frac{1}{n}\sum_{k=1}^{n}G_{\mu_{k}}(\xi)\
\ \ \xi\in\mathbb{C}^{+},$

and by the Equation (1) it follows that:

$\mu_{s}=\frac{1}{n}\sum_{k=1}^{n}\mu_{k},$

proving the desired result. ∎

## Acknowledgement

The author would like to express his thanks to Prof. Serban Belinschi for his
guidance and support on this paper.

## References

  * [1] Choi, M. D. (1975). Completely Positive Linear Maps on Complex Matrices, Linear Algebra and Its Applications, 10, pp. 285-290,
  * [2] Cox, D, Little, J, and O’shea, D. (2007). Ideals, Varieties, and Algorithms, 3rd edistion, Springer, pp. 96-98,
  * [3] Helton, W, Rashidi Far, R, and Speicher, R. (2007). Operator-Valued Semicircular Elements: Solving a Quadratic Matrix Equation with Positivity Constraints, IMRN , Vol. 2007, Article ID rnm086, 15 pages,
  * [4] Hora, A, and Obata, N. (2007). Quantum Probability and Spectral Analysis of Graphs, Springer, pp. 51-61,
  * [5] Paulsen, V. (2003). Completely Bounded Maps and Operator Algebras, Cambridge University Press,
  * [6] Rashidi Far, R, Oraby, T, Bryc, W, and Speicher, R. (2008). On Slow-fading MIMO Systems with Nonseparable Correlation, IEEE Trans. Inform. Theory No 2, Vol 54, pp. 544-553,
  * [7] Shlyakhtenko, D. (1996). Random Guassian Band Matrices and Freeness with Amalgamation, IMRN, No 20, pp. 1013-1025,
  * [8] Shohat, J. A. and Tamarkin, J. D. (1943). The Problem of Moments, American Mathematical Society, pp. 23-26,
  * [9] Speicher, R. (1998). Combinatorial Theory of the Free Product With Amalgamation and Operator-Valued Free Probability Theory, Memories of Amer. Math. Soc. 132,
  * [10] Voiculescu, D. V. (1991). Limit Laws for Random Matrices and Free Products, Invent. Math, No 1, Vol 104, pp. 201-220,
  * [11] Voiculescu, D. V. (1995). Operations on Certain Non-Commutative Operator Valued Random Variables, Astérisque, No 2, pp. 243-275,
  * [12] Wigner E. P. (1958). On the Distributions of the Roots of Certain Symmetric Matrices, Ann. of Math, No 2, Vol 67, pp. 325-327