| dc.description.abstract | The analysis of similarity of matrices over fields, as well as integral domains which are not fields, is a classical problem in Linear Algebra and has received considerable attention. A related problem is that of simultaneous similarity of matrices. Many interesting algebraic questions that arise in such problems are discussed by Shmuel Friedland[1]. A special case of this problem is that of Simultaneous Unitary Similarity of hermitian matrices, which we describe as follows:
Given a collection of m ordered pairs of similar n×n hermitian matrices denoted by {(Hl,Dl)}ml=1,
1. determine if there exists a unitary matrix U such that
UHl U∗ = Dl for all l,
2. and in the case where a U exists, find such a U,
(where U∗is the transpose conjugate of U ).The problem is easy for m =1. The problem is challenging for m > 1.The problem stated above is the algorithmic version of the problem of classifying hermitian matrices upto unitary similarity. Any problem involving classification of matrices up to similarity is considered to be “wild”[2]. The difficulty in solving the problem of classifying matrices up to unitary similarity is a indicator of, the toughness of problems involving matrices in unitary spaces [3](pg, 44-46 ).Suppose in the statement of the problem we replace the collection {(Hl,Dl)}ml=1, by a collection of m ordered pairs of complex square matrices denoted by {(Al,Bl) ml=1, then we get the Simultaneous Unitary Similarity problem for square matrices.
Suppose we consider k ordered pairs of complex rectangular m ×n matrices denoted by {(Yl,Zl)}kl=1, then the Simultaneous Unitary Equivalence problem for rectangular matrices is the problem of finding whether there exists a m×m unitary matrix U and a n×n unitary matrix V such that UYlV ∗= Zl for all l and in the case they exist find them. In this thesis we describe algorithms to solve these problems.
The Simultaneous Unitary Similarity problem for square matrices is challenging for even a single pair (m = 1) if the matrices involved i,e A1,B1 are not normal. In an expository article, Shapiro[4]describes the methods available to solve this problem by arriving at a canonical form. That is A1 or B1 is used to arrive at a canonical form and the matrices are unitarily similar if and only if the other matrix also leads to the same canonical form.
In this thesis, in the second chapter we propose an iterative algorithm to solve the Simultaneous Unitary Similarity problem for hermitian matrices. In each iteration we either get a step closer to “the simple case” or end up solving the problem. The simple case which we describe in detail in the first chapter corresponds to finding whether there exists a diagonal unitary matrix U such that UHlU∗= Dl for all l. Solving this case involves defining “paths” made up of non-zero entries of Hl (or Dl). We use these paths to define an equivalence relation that partitions L = {1,…n}. Using these paths we associate scalars with each Hl(i,j) and Dl(i,j)denoted by pr(Hl(i,j)) and pr(Dl(i,j)) (pr is used to indicate that these scalars are obtained by considering products of non-zero elements along the paths from i,j to their class representative). Suppose i (I Є L)belongs to the class[d(i)](d(i) Є L) we denote by uisol a modulus one scalar expressed in terms of ud(i) using the path from i to d( i). The free variable ud(i) can be chosen to be any modulus one scalar. Let U sol be a diagonal unitary matrix given by U sol = diag(u1 sol , u2 sol , unsol ).
We show that a diagonal U such that U HlU∗ = Dl exists if and only if pr(Hl(i, j)) = pr(Dl(i, j))for all l, i, j and UsolHlUsol∗= Dl. Solving the simple case sets the trend for solving the general case.
In the general case in an iteration we are looking for a unitary U such that U = blk −diag(U1,…, Ur) where each Ui is a pi ×p (i, j Є L = {1,… , r}) unitary matrix such that U HlU ∗= Dl. Our aim in each iteration is to get at least a step closer to the simple case. Based on pi we partition the rows and columns of Hl and Dl to obtain pi ×pj sub-matrices denoted by Flij in Hl and Glij in D1. The aim is to diagonalize either Flij∗Flij Flij∗ and a
get a step closer to the simple case. If square sub-matrices are multiples of unitary and rectangular sub-matrices are zeros we say that the collection is in Non-reductive-form and in this case we cannot get a step closer to the simple case.
In Non- reductive-form just as in the simple case we define a relation on L using paths made up of these non-zero (multiples of unitary) sub-matrices. We have a partition of L. Using these paths we associate with Flij and (G1ij ) matrices denoted by pr(F1ij) and pr(G1ij) respectively where pr(F1ij) and pr(G1ij) are multiples of unitary. If there exist pr(Flij) which are not multiples of identity then we diagonalize these matrices and move a step closer to the simple case and the given collection is said to be in Reduction-form. If not, the collection is in Solution-form. In Solution-form we identify a unitary matrix U sol = blk −diag(U1sol , U2 sol , …, Ur sol )where U isol is a pi ×pi
unitary matrix that is expressed in terms of Ud(i) by using the path from i to[d(i)]( i Є [d(i)], d(i) Є L, Ud(i) is free). We show that there exists U such that U HlU∗ = Dl if and only if pr((Flij) = pr(G1ij) and U solHlU sol∗ = Dl. Thus in a maximum of n steps the algorithm solves the Simultaneous Unitary Similarity problem for hermitian matrices. In the second chapter we also relate the Simultaneous Unitary Similarity problem for hermitian matrices to the simultaneous closed system evolution problem for quantum states.
In the third chapter we describe algorithms to solve the Unitary Similarity problem for square matrices (single ordered pair) and the Simultaneous Unitary Equivalence problem for rectangular matrices. These problems are related to the Simultaneous Unitary Similarity problem for hermitian matrices. The algorithms described in this chapter are similar in flow to the algorithm described in the second chapter. This shows that it is the fact that we are looking for unitary similarity that makes these forms possible. The hermitian (or normal)nature of the matrices is of secondary importance. Non-reductive-form is the same as in the hermitian case. The definition of the paths changes a little. But once the paths are defined and the set L is partitioned the definitions of Reduction-form and Solution-form are similar to their counterparts in the hermitian case.
In the fourth chapter we analyze the worst case complexity of the proposed algorithms. The main computation in all these algorithms is that of diagonalizing normal matrices, partitioning L and calculating the products pr((Flij) = pr(G1ij). Finding the partition of L is like partitioning an undirected graph in the square case and partitioning a bi-graph in the rectangular case. Also, in this chapter we demonstrate the working of the proposed algorithms by running through the steps of the algorithms for three examples.
In the fifth and the final chapter we show that finding if a given collection of ordered pairs of normal matrices is Simultaneously Similar is same as finding if the collection is Simultaneously Unitarily Similar. We also discuss why an algorithm to solve the Simultaneous Similarity problem, along the lines of the algorithms we have discussed in this thesis, may not exist. (For equations pl refer the pdf file) | en_US |
