Feed aggregator

Resolution Of Conjectures Related To Lights Out! And Cartesian Products

WySR RSS Feed - Wed, 2019-01-16 22:12

Lights Out!\ is a game played on a $5 \times 5$ grid of lights, or more generally on a graph. Pressing lights on the grid allows the player to turn off neighboring lights. The goal of the game is to start with a given initial configuration of lit lights and reach a state where all lights are out. Two conjectures posed in a recently published paper about Lights Out!\ on Cartesian products of graphs are resolved.

On the Interval Generalized Coupled Matrix Equations

WySR RSS Feed - Wed, 2019-01-16 22:12

In this work, the interval generalized coupled matrix equations \begin{equation*} \sum_{j=1}^{p}{{\bf{A}}_{ij}X_{j}}+\sum_{k=1}^{q}{Y_{k}{\bf{B}}_{ik}}={\bf{C}}_{i}, \qquad i=1,\ldots,p+q, \end{equation*} are studied in which ${\bf{A}}_{ij}$, ${\bf{B}}_{ik}$ and ${\bf{C}}_{i}$ are known real interval matrices, while $X_{j}$ and $Y_{k}$ are the unknown matrices for $j=1,\ldots,p$, $k=1,\ldots,q$ and $i=1,\ldots,p+q$. This paper discusses the so-called AE-solution sets for this system. In these types of solution sets, the elements of the involved interval matrices are quantified and all occurrences of the universal quantifier $\forall$ (if any) precede the occurrences of the existential quantifier $\exists$. The AE-solution sets are characterized and some sufficient conditions under which these types of solution sets are bounded are given. Also some approaches are proposed which include a numerical technique and an algebraic approach for enclosing some types of the AE-solution sets.

A note on linear preservers of semipositive and minimally semipositive matrices

WySR RSS Feed - Tue, 2019-01-08 12:59

Semipositive matrices (matrices that map at least one nonnegative vector to a positive vector) and minimally semipositive matrices (semipositive matrices whose no column-deleted submatrix is semipositive) are well studied in matrix theory. In this short note, the structure of linear maps which preserve the set of all semipositive/minimally semipositive matrices is studied. An open problem is solved, and some ambiguities in the article [J. Dorsey, T. Gannon, N. Jacobson, C.R. Johnson and M. Turnansky. Linear preservers of semi-positive matrices. {\em Linear and Multilinear Algebra}, 64:1853--1862, 2016.] are clarified.

Vector Cross Product Differential and Difference Equations in R^3 and in R^7

WySR RSS Feed - Tue, 2019-01-08 12:58

Through a matrix approach of the $2$-fold vector cross product in $\mathbb{R}^3$ and in $\mathbb{R}^7$, some vector cross product differential and difference equations are studied. Either the classical theory or convenient Drazin inverses, of elements belonging to the class of index $1$ matrices, are applied.

Gershgorin type sets for eigenvalues of matrix polynomials

WySR RSS Feed - Wed, 2018-12-26 16:32

New localization results for polynomial eigenvalue problems are obtained, by extending the notions of the Gershgorin set, the generalized Gershgorin set, the Brauer set and the Dashnic-Zusmanovich set to the case of matrix polynomials.

Determinantal Properties of Generalized Circulant Hadamard Matrices

WySR RSS Feed - Wed, 2018-12-26 16:31

The derivation of analytical formulas for the determinant and the minors of a given matrix is in general a difficult and challenging problem. The present work is focused on calculating minors of generalized circulant Hadamard matrices. The determinantal properties are studied explicitly, and generic theorems specifying the values of all the minors for this class of matrices are derived. An application of the derived formulae to an interesting problem of numerical analysis, the growth problem, is also presented.

On the Condition Number Theory of the Equality Constrained Indefinite Least Squares Problem

WySR RSS Feed - Wed, 2018-12-26 16:31

In this paper, within a unified framework of the condition number theory, the explicit expression of the \emph{projected} condition number of the equality constrained indefinite least squares problem is presented. By setting specific norms and parameters, some widely used condition numbers, like the normwise, mixed and componentwise condition numbers follow as its special cases. Considering practical applications and computation, some new compact forms or upper bounds of the projected condition numbers are given to improve the computational efficiency. The new compact forms are of particular interest in calculating the exact value of the 2-norm projected condition numbers. When the equality constrained indefinite least squares problem degenerates into some specific least squares problems, our results give some new findings on the condition number theory of these specific least squares problems. Numerical experiments are given to illustrate our theoretical results.

Ordering cacti with signless Laplacian spread

WySR RSS Feed - Thu, 2018-12-13 10:14

A cactus is a connected graph in which any two cycles have at most one vertex in common. The signless Laplacian spread of a graph is defined as the difference between the largest eigenvalue and the smallest eigenvalue of the associated signless Laplacian matrix. In this paper, all cacti of order n with signless Laplacian spread greater than or equal to n − 1/2 are determined.

Two linear preserver problems on graphs

WySR RSS Feed - Thu, 2018-12-13 10:14

Let n, t, k be integers such that 3 ≤ t,k ≤ n. Denote by G_n the set of graphs with vertex set {1,2,...,n}. In this paper, the complete linear transformations on G_n mapping K_t-free graphs to K_t-free graphs are characterized. The complete linear transformations on G_n mapping C_k-free graphs to C_k-free graphs are also characterized when n ≥ 6.

Discontinuity Propagation in Delay Differential-Algebraic Equations

WySR RSS Feed - Sun, 2018-12-09 19:22

The propagation of primary discontinuities in initial value problems for linear delay differential-algebraic equations (DDAEs) is discussed. Based on the (quasi-) Weierstra{\ss} form for regular matrix pencils, a complete characterization of the different propagation types is given and algebraic criteria in terms of the matrices are developed. The analysis, which is based on the method of steps, takes into account all possible inhomogeneities and history functions and thus serves as a worst-case scenario. Moreover, it reveals possible hidden delays in the DDAE and allows to study exponential stability of the DDAE based on the spectral abscissa. The new classification for DDAEs is compared to existing approaches in the literature and the impact of splicing conditions on the classification is studied.

Asymptotic results on the condition number of FD matrices approximating semi-elliptic PDEs

WySR RSS Feed - Sun, 2018-12-09 19:22

This work studies the asymptotic behavior of the spectral condition number of the matrices $A_{nn}$ arising from the discretization of semi-elliptic partial differential equations of the form \bdm -\left( a(x,y)u_{xx}+b(x,y)u_{yy}\right)=f(x,y), \edm on the square $\Omega=(0,1)^2,$ with Dirichlet boundary conditions, where the smooth enough variable coefficients $a(x,y), b(x,y)$ are nonnegative functions on $\overline{\Omega}$ with zeros. In the case of coefficient functions with a single and common zero, it is discovered that apart from the minimum order of the zero also the direction that it occurs is of great importance for the characterization of the growth of the condition number of $A_{nn}$. On the contrary, when the coefficient functions have non intersecting zeros, it is proved that independently of the order their zeros, and their positions, the condition number of $A_{nn}$ behaves asymptotically exactly as in the case of strictly elliptic differential equations, i.e., it grows asymptotically as $n^2$. Finally, the more complicated case of coefficient functions having curves of roots is considered, and conjectures for future work are given. In conclusion, several experiments are presented that numerically confirm the developed theoretical analysis.

REGULARITY RADIUS: PROPERTIES, APPROXIMATION AND A NOT A PRIORI EXPONENTIAL ALGORITHM

WySR RSS Feed - Thu, 2018-12-06 02:30

The radius of regularity, sometimes spelled as the radius of nonsingularity, is a measure providing the distance of a given matrix to the nearest singular one. Despite its possible application strength this measure is still far from being handled in an efficient way also due to findings of Poljak and Rohn providing proof that checking this property is NP-hard for a general matrix. There are basically two approaches to handle this situation. Firstly, approximation algorithms are applied and secondly, tighter bounds for radius of regularity are considered. Improvements of both approaches have been recently shown by Hartman and Hlad\'{i}k (doi:10.1007/978-3-319-31769-4\_9) utilizing relaxation of the radius computation to semidefinite programming. An estimation of the regularity radius using any of the above mentioned approaches is usually applied to general matrices considering none or just weak assumptions about the original matrix. Surprisingly less explored area is represented by utilization of properties of special classes of matrices as well as utilization of classical algorithms extended to be used to compute the considered radius. This work explores a process of regularity radius analysis and identifies useful properties enabling easier estimation of the corresponding radius values. At first, checking finiteness of this characteristic is shown to be a polynomial problem along with determining a sharp upper bound on the number of nonzero elements of the matrix to obtain infinite radius. Further, relationship between maximum (Chebyshev) norm and spectral norm is used to construct new bounds for the radius of regularity. Considering situations where the known bounds are not tight enough, a new method based on Jansson-Rohn algorithm for testing regularity of an interval matrix is presented which is not a priory exponential along with numerical experiments. For a situation where an input matrix has a special form, several corresponding results are provided such as exact formulas for several special classes of matrices, e.g., for totally positive and inverse non-negative, or approximation algorithms, e.g., rank-one radius matrices. For tridiagonal matrices, an algorithm by Bar-On, Codenotti and Leoncini is utilized to design a polynomial algorithm to compute the radius of regularity.

Commutators Involving Matrix Functions

WySR RSS Feed - Fri, 2018-11-30 10:32

Some results are obtained for matrix commutators involving matrix exponentials $\left(\left[e^{A},B\right],\left[e^{A},e^{B}\right]\right)$ and their norms.

Determinants of Interval Matrices

WySR RSS Feed - Mon, 2018-11-19 08:16

In this paper we shed more light on determinants of real interval matrices. Computing the exact bounds on a determinant of an interval matrix is an NP-hard problem. Therefore, attention is first paid to approximations. NP-hardness of both relative and absolute approximation is proved. Next, methods computing verified enclosures of interval determinants and their possible combination with preconditioning are discussed. A new method based on Cramer's rule was designed. It returns similar results to the state-of-the-art method, however, it is less consuming regarding computational time. Other methods transferable from real matrices (e.g., the Gerschgorin circles, Hadamard's inequality) are discussed. New results about classes of interval matrices with polynomially computable tasks related to determinant are proved (symmetric positive definite matrices, class of matrices with identity midpoint matrix, tridiagonal H-matrices). The mentioned methods were compared for random general and symmetric matrices.

Inequalities between $\mid A\mid + \mid B\mid $ and $\mid A^{*} \mid + \mid B^{*} \mid$

WySR RSS Feed - Sat, 2018-11-17 02:14

Let $A$ and $B$ be complex square matrices. Some inequalities between $\mid A \mid + \mid B \mid$ and $\mid A^{*} \mid + \mid B^{*} \mid$ are established. Applications of these inequalities are also given. For example, in the Frobenius norm, $$ \parallel\, A+B \,\parallel_{F} \leq \sqrt[4]{2} \parallel \mid A\mid + \mid B\mid \, \parallel_{F}. $$

Structured eigenvalue/eigenvector backward errors of matrix pencils arising in optimal control

WySR RSS Feed - Sat, 2018-11-17 02:14

Eigenvalue and eigenpair backward errors are computed for matrix pencils arising in optimal control. In particular, formulas for backward errors are developed that are obtained under block-structure-preserving and symmetry-structure-preserving perturbations. It is shown that these eigenvalue and eigenpair backward errors are sometimes significantly larger than the corresponding backward errors that are obtained under perturbations that ignore the special structure of the pencil.

Perturbation results and the forward order law for the Moore-Penrose inverse of a product

WySR RSS Feed - Wed, 2018-11-14 20:57

New expressions are given for the Moore-Penrose inverse of a product $AB$ of two complex matrices. Furthermore, an expression for $(AB)\dg - B\dg A\dg$ for the case where $A$ or $B$ is of full rank is provided. Necessary and sufficient conditions for the forward order law for the Moore-Penrose inverse of a product to hold are established. The perturbation results presented in this paper are applied to characterize some mixed-typed reverse order laws for the Moore-Penrose inverse, as well as the reverse order law.

Convergence of a modified Newton method for a matrix polynomial equation arising in stochastic problem

WySR RSS Feed - Mon, 2018-11-12 23:01

The Newton iteration is considered for a matrix polynomial equation which arises in stochastic problem. In this paper, it is shown that the elementwise minimal nonnegative solution of the matrix polynomial equation can be obtained using Newton's method if the equation satisfies the sufficient condition, and the convergence rate of the iteration is quadratic if the solution is simple. Moreover, it is shown that the convergence rate is at least linear if the solution is non-simple, but a modified Newton method whose iteration number is less than the pure Newton iteration number can be applied. Finally, numerical experiments are given to compare the effectiveness of the modified Newton method and the standard Newton method.

Estimators Comparison of Separable Covariance Structure with One Component as Compound Symmetry Matrix

WySR RSS Feed - Mon, 2018-11-05 17:57

The maximum likelihood estimation (MLE) of separable covariance structure with one component as compound symmetry matrix has been widely studied in the literature. Nevertheless, the proposed estimates are not given in explicit form and can be determined only numerically. In this paper we give an alternative form of MLE and we show that this new algorithm is much quicker than the algorithms given in the literature.\\ Another estimator of covariance structure can be found by minimizing the entropy loss function. In this paper we give three methods of finding the best approximation of separable covariance structure with one component as compound symmetry matrix and we compare the quickness of proposed algorithms.\\ We conduct simulation studies to compare statistical properties of MLEs and entropy loss estimators (ELEs), such us biasedness, variability and loss. Another estimator of covariance structure can be found by minimizing the entropy loss function. In this paper we give three methods of finding the best approximation of separable covariance structure with one component as compound symmetry matrix and we compare the quickness of proposed algorithms. We conduct simulation studies to compare statistical properties of MLEs and entropy loss estimators (ELEs), such us biasedness and variability.

On Projection of a Positive Definite Matrix on a Cone of Nonnegative Definite Toeplitz Matrices

WySR RSS Feed - Fri, 2018-10-12 14:20

We consider approximation of a given positive definite matrix by nonnegative definite banded Toeplitz matrices. We show that the projection on linear space of Toeplitz matrices does not always preserve nonnegative definiteness. Therefore we characterize a convex cone of nonnegative definite banded Toeplitz matrices which depends on the matrix dimensions, and we show that the condition of positive definiteness given by Parter [{\em Numer. Math. 4}, 293--295, 1962] characterizes the asymptotic cone. In this paper we give methodology and numerical algorithm of the projection basing on the properties of a cone of nonnegative definite Toeplitz matrices. This problem can be applied in statistics, for example in the estimation of unknown covariance structures under the multi-level multivariate models, where positive definiteness is required. We conduct simulation studies to compare statistical properties of the estimators obtained by projection on the cone with a given matrix dimension and on the asymptotic cone.

Pages

Subscribe to UW Digital aggregator