Matrices whose hermitian part is positive definite

We are concerned with the class ∏_n of nxn complex matrices A for which the Hermitian part H(A) = A+A*/2 is positive definite.

Various connections are established with other classes such as the stable, D-stable and dominant diagonal matrices. For instance it is proved that if there exist positive diagonal matrices D, E such that DAE is either row dominant or column dominant and has positive diagonal entries, then there is a positive diagonal F such that FA ϵ ∏_n.

Powers are investigated and it is found that the only matrices A for which A^m ϵ ∏_n for all integers m are the Hermitian elements of ∏_n. Products and sums are considered and criteria are developed for AB to be in ∏_n.

Since ∏_n n is closed under inversion, relations between H(A)^-1 and H(A^-1) are studied and a dichotomy observed between the real and complex cases. In the real case more can be said and the initial result is that for A ϵ ∏_n, the difference H(adjA) - adjH(A) ≥ 0 always and is ˃ 0 if and only if S(A) = A-A*/2 has more than one pair of conjugate non-zero characteristic roots. This is refined to characterize real c for which cH(A^-1) - H(A)^-1 is positive definite.

The cramped (characteristic roots on an arc of less than 180°) unitary matrices are linked to ∏_n and characterized in several ways via products of the form A ^-1A*.

Classical inequalities for Hermitian positive definite matrices are studied in ∏_n and for Hadamard's inequality two types of generalizations are given. In the first a large subclass of ∏_n in which the precise statement of Hadamardis inequality holds is isolated while in another large subclass its reverse is shown to hold. In the second Hadamard's inequality is weakened in such a way that it holds throughout ∏_n. Both approaches contain the original Hadamard inequality as a special case.

Transceiver designs and analysis for LTI, LTV and broadcast channels - new matrix decompositions and majorization theory

Signal processing techniques play important roles in the design of digital communication systems. These include information manipulation, transmitter signal processing, channel estimation, channel equalization and receiver signal processing. By interacting with communication theory and system implementing technologies, signal processing specialists develop efficient schemes for various communication problems by wisely exploiting various mathematical tools such as analysis, probability theory, matrix theory, optimization theory, and many others. In recent years, researchers realized that multiple-input multiple-output (MIMO) channel models are applicable to a wide range of different physical communications channels. Using the elegant matrix-vector notations, many MIMO transceiver (including the precoder and equalizer) design problems can be solved by matrix and optimization theory. Furthermore, the researchers showed that the majorization theory and matrix decompositions, such as singular value decomposition (SVD), geometric mean decomposition (GMD) and generalized triangular decomposition (GTD), provide unified frameworks for solving many of the point-to-point MIMO transceiver design problems.

In this thesis, we consider the transceiver design problems for linear time invariant (LTI) flat MIMO channels, linear time-varying narrowband MIMO channels, flat MIMO broadcast channels, and doubly selective scalar channels. Additionally, the channel estimation problem is also considered. The main contributions of this dissertation are the development of new matrix decompositions, and the uses of the matrix decompositions and majorization theory toward the practical transmit-receive scheme designs for transceiver optimization problems. Elegant solutions are obtained, novel transceiver structures are developed, ingenious algorithms are proposed, and performance analyses are derived.

The first part of the thesis focuses on transceiver design with LTI flat MIMO channels. We propose a novel matrix decomposition which decomposes a complex matrix as a product of several sets of semi-unitary matrices and upper triangular matrices in an iterative manner. The complexity of the new decomposition, generalized geometric mean decomposition (GGMD), is always less than or equal to that of geometric mean decomposition (GMD). The optimal GGMD parameters which yield the minimal complexity are derived. Based on the channel state information (CSI) at both the transmitter (CSIT) and receiver (CSIR), GGMD is used to design a butterfly structured decision feedback equalizer (DFE) MIMO transceiver which achieves the minimum average mean square error (MSE) under the total transmit power constraint. A novel iterative receiving detection algorithm for the specific receiver is also proposed. For the application to cyclic prefix (CP) systems in which the SVD of the equivalent channel matrix can be easily computed, the proposed GGMD transceiver has K/log_2(K) times complexity advantage over the GMD transceiver, where K is the number of data symbols per data block and is a power of 2. The performance analysis shows that the GGMD DFE transceiver can convert a MIMO channel into a set of parallel subchannels with the same bias and signal to interference plus noise ratios (SINRs). Hence, the average bit rate error (BER) is automatically minimized without the need for bit allocation. Moreover, the proposed transceiver can achieve the channel capacity simply by applying independent scalar Gaussian codes of the same rate at subchannels.

In the second part of the thesis, we focus on MIMO transceiver design for slowly time-varying MIMO channels with zero-forcing or MMSE criterion. Even though the GGMD/GMD DFE transceivers work for slowly time-varying MIMO channels by exploiting the instantaneous CSI at both ends, their performance is by no means optimal since the temporal diversity of the time-varying channels is not exploited. Based on the GTD, we develop space-time GTD (ST-GTD) for the decomposition of linear time-varying flat MIMO channels. Under the assumption that CSIT, CSIR and channel prediction are available, by using the proposed ST-GTD, we develop space-time geometric mean decomposition (ST-GMD) DFE transceivers under the zero-forcing or MMSE criterion. Under perfect channel prediction, the new system minimizes both the average MSE at the detector in each space-time (ST) block (which consists of several coherence blocks), and the average per ST-block BER in the moderate high SNR region. Moreover, the ST-GMD DFE transceiver designed under an MMSE criterion maximizes Gaussian mutual information over the equivalent channel seen by each ST-block. In general, the newly proposed transceivers perform better than the GGMD-based systems since the super-imposed temporal precoder is able to exploit the temporal diversity of time-varying channels. For practical applications, a novel ST-GTD based system which does not require channel prediction but shares the same asymptotic BER performance with the ST-GMD DFE transceiver is also proposed.

The third part of the thesis considers two quality of service (QoS) transceiver design problems for flat MIMO broadcast channels. The first one is the power minimization problem (min-power) with a total bitrate constraint and per-stream BER constraints. The second problem is the rate maximization problem (max-rate) with a total transmit power constraint and per-stream BER constraints. Exploiting a particular class of joint triangularization (JT), we are able to jointly optimize the bit allocation and the broadcast DFE transceiver for the min-power and max-rate problems. The resulting optimal designs are called the minimum power JT broadcast DFE transceiver (MPJT) and maximum rate JT broadcast DFE transceiver (MRJT), respectively. In addition to the optimal designs, two suboptimal designs based on QR decomposition are proposed. They are realizable for arbitrary number of users.

Finally, we investigate the design of a discrete Fourier transform (DFT) modulated filterbank transceiver (DFT-FBT) with LTV scalar channels. For both cases with known LTV channels and unknown wide sense stationary uncorrelated scattering (WSSUS) statistical channels, we show how to optimize the transmitting and receiving prototypes of a DFT-FBT such that the SINR at the receiver is maximized. Also, a novel pilot-aided subspace channel estimation algorithm is proposed for the orthogonal frequency division multiplexing (OFDM) systems with quasi-stationary multi-path Rayleigh fading channels. Using the concept of a difference co-array, the new technique can construct M^2 co-pilots from M physical pilot tones with alternating pilot placement. Subspace methods, such as MUSIC and ESPRIT, can be used to estimate the multipath delays and the number of identifiable paths is up to O(M^2), theoretically. With the delay information, a MMSE estimator for frequency response is derived. It is shown through simulations that the proposed method outperforms the conventional subspace channel estimator when the number of multipaths is greater than or equal to the number of physical pilots minus one.

Discovery of non-zero neutrino mixing angle θ_13 using Daya Bay antineutrino detectors

The Daya Bay Reactor Antineutrino Experiment observed the disappearance of reactor $\bar{\nu}_e$ from six $2.9~GW_{th}$ reactor cores in Daya Bay, China. The Experiment consists of six functionally identical $\bar{\nu}_e$ detectors, which detect $\bar{\nu}_e$ by inverse beta decay using a total of about 120 metric tons of Gd-loaded liquid scintillator as the target volume. These $\bar{\nu}_e$ detectors were installed in three underground experimental halls, two near halls and one far hall, under the mountains near Daya Bay, with overburdens of 250 m.w.e, 265 m.w.e and 860 m.w.e. and flux-weighted baselines of 470 m, 576 m and 1648 m. A total of 90179 $\bar{\nu}_e$ candidates were observed in the six detectors over a period of 55 days, 57549 at the Daya Bay near site, 22169 at the Ling Ao near site and 10461 at the far site. By performing a rate-only analysis, the value of $sin^2 2\theta_{13}$ was determined to be $0.092 \pm 0.017$.

Diagonal forms, linear algebraic methods and Ramsey-type problems

This thesis focuses mainly on linear algebraic aspects of combinatorics. Let N_t(H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of N_t(H) for all simple graphs H and for a very general class of t-uniform hypergraphs H.

As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets.

One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro's results in zero-sum Ramsey numbers for graphs and Caro and Yuster's results in zero-sum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs.

Research results on some other problems are also included in this thesis, such as a Ramsey-type problem on equipartitions, Hartman's conjecture on large sets of designs and a matroid theory problem proposed by Welsh.

Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).

Transmission matrices and lumped parameter models for continuous systems

The use of transmission matrices and lumped parameter models for describing continuous systems is the subject of this study. Non-uniform continuous systems which play important roles in practical vibration problems, e.g., torsional oscillations in bars, transverse bending vibrations of beams, etc., are of primary importance.

A new approach for deriving closed form transmission matrices is applied to several classes of non-uniform continuous segments of one dimensional and beam systems. A power series expansion method is presented for determining approximate transmission matrices of any order for segments of non-uniform systems whose solutions cannot be found in closed form. This direct series method is shown to give results comparable to those of the improved lumped parameter models for one dimensional systems.

Four types of lumped parameter models are evaluated on the basis of the uniform continuous one dimensional system by comparing the behavior of the frequency root errors. The lumped parameter models which are based upon a close fit to the low frequency approximation of the exact transmission matrix, at the segment level, are shown to be superior. On this basis an improved lumped parameter model is recommended for approximating non-uniform segments. This new model is compared to a uniform segment approximation and error curves are presented for systems whose areas very quadratically and linearly. The effect of varying segment lengths is investigated for one dimensional systems and results indicate very little improvement in comparison to the use of equal length segments. For purposes of completeness, a brief summary of various lumped parameter models and other techniques which have previously been used to approximate the uniform Bernoulli-Euler beam is a given.

Part I. Approximate Hartree-Fock wavefunctions one-electron properties and electronic structure of the water molecule. Part II. Perturbation-variational calculation of the nuclear spin-spin isotope coupling constant in HD

Part I

Several approximate Hartree-Fock SCF wavefunctions for the ground electronic state of the water molecule have been obtained using an increasing number of multicenter s, p, and d Slater-type atomic orbitals as basis sets. The predicted charge distribution has been extensively tested at each stage by calculating the electric dipole moment, molecular quadrupole moment, diamagnetic shielding, Hellmann-Feynman forces, and electric field gradients at both the hydrogen and the oxygen nuclei. It was found that a carefully optimized minimal basis set suffices to describe the electronic charge distribution adequately except in the vicinity of the oxygen nucleus. Our calculations indicate, for example, that the correct prediction of the field gradient at this nucleus requires a more flexible linear combination of p-orbitals centered on this nucleus than that in the minimal basis set. Theoretical values for the molecular octopole moment components are also reported.

Part II

The perturbation-variational theory of R. M. Pitzer for nuclear spin-spin coupling constants is applied to the HD molecule. The zero-order molecular orbital is described in terms of a single 1s Slater-type basis function centered on each nucleus. The first-order molecular orbital is expressed in terms of these two functions plus one singular basis function each of the types e^-r/r and e^-r ln r centered on one of the nuclei. The new kinds of molecular integrals were evaluated to high accuracy using numerical and analytical means. The value of the HD spin-spin coupling constant calculated with this near-minimal set of basis functions is J_HD = +96.6 cps. This represents an improvement over the previous calculated value of +120 cps obtained without using the logarithmic basis function but is still considerably off in magnitude compared with the experimental measurement of J_HD = +43 0 ± 0.5 cps.

On the Lyapunov transformation for stable matrices

The matrices studied here are positive stable (or briefly stable). These are matrices, real or complex, whose eigenvalues have positive real parts. A theorem of Lyapunov states that A is stable if and only if there exists H ˃ 0 such that AH + HA* = I. Let A be a stable matrix. Three aspects of the Lyapunov transformation L_A :H → AH + HA* are discussed.

1. Let C₁ (A) = {AH + HA* :H ≥ 0} and C₂ (A) = {H: AH+HA* ≥ 0}. The problems of determining the cones C₁(A) and C₂(A) are still unsolved. Using solvability theory for linear equations over cones it is proved that C₁(A) is the polar of C₂(A*), and it is also shown that C₁ (A) = C₁(A^-1). The inertia assumed by matrices in C₁(A) is characterized.

2. The index of dissipation of A was defined to be the maximum number of equal eigenvalues of H, where H runs through all matrices in the interior of C₂(A). Upper and lower bounds, as well as some properties of this index, are given.

3. We consider the minimal eigenvalue of the Lyapunov transform AH+HA*, where H varies over the set of all positive semi-definite matrices whose largest eigenvalue is less than or equal to one. Denote it by ψ(A). It is proved that if A is Hermitian and has eigenvalues μ₁ ≥ μ₂…≥ μ_n ˃ 0, then ψ(A) = -(μ₁-μ_n)²/(4(μ₁ + μ_n)). The value of ψ(A) is also determined in case A is a normal, stable matrix. Then ψ(A) can be expressed in terms of at most three of the eigenvalues of A. If A is an arbitrary stable matrix, then upper and lower bounds for ψ(A) are obtained.