A noncommutative version of the matrix inversion formula

The cofactor expression (? 1)^i+j$\text{det}\text{(I ? B)}{}_{\mathrm{<mtext>j</mtext><mtext>?</mtext><mtext>i</mtext><mtext>?</mtext>}}\text{det}\text{(I ? B)}$ for the (i, j)-entry in the inverse of a matrix (I ? B) is proved to be equal to the corresponding entry of the series Σ_m≥0B^m, by using purely combinatorial methods: circuit monoid techniques and monomial rearrangements. Moreover, the identity is shown to hold in a non-commutative formal power series algebra.     

Retaining positive definiteness in thresholded matrices

Positive definite (p.d.) matrices arise naturally in many areas within mathematics and also feature extensively in scientific applications. In modern high-dimensional applications, a common approach to finding sparse positive definite matrices is to threshold their small off-diagonal elements. This thresholding, sometimes referred to as hard-thresholding, sets small elements to zero. Thresholding has the attractive property that the resulting matrices are sparse, and are thus easier to interpret and work with. In many applications, it is often required, and thus implicitly assumed, that thresholded matrices retain positive definiteness. In this paper we formally investigate the algebraic properties of p.d. matrices which are thresholded. We demonstrate that for positive definiteness to be preserved, the pattern of elements to be set to zero has to necessarily correspond to a graph which is a union of complete components. This result rigorously demonstrates that, except in special cases, positive definiteness can be easily lost. We then proceed to demonstrate that the class of diagonally dominant matrices is not maximal in terms of retaining positive definiteness when thresholded. Consequently, we derive characterizations of matrices which retain positive definiteness when thresholded with respect to important classes of graphs. In particular, we demonstrate that retaining positive definiteness upon thresholding is governed by complex algebraic conditions.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Sensitivity of trust-region algorithms to their parameters

In this paper, we examine the sensitivity of trust-region algorithms on the parameters related to the step acceptance and update of the trust region. We show, in the context of unconstrained programming, that the numerical efficiency of these algorithms can easily be improved by choosing appropriate parameters. Recommended ranges of values for these parameters are exhibited on the basis of extensive numerical tests. MSC classification: 65K05, 90C26, 90C30     

Tail Behavior of a Threshold Autoregressive Stochastic Volatility Model

We consider a threshold autoregressive stochastic volatility model where the driving noises are sequences of iid regularly random variables. We prove that both the right and the left tails of the marginal distribution of the log-volatility process (α_t)_t are regularly varying with tail exponent −α with α > 0. We also determine the exact values of the coefficients in the tail behaviour of the process (α_t)_t. AMS 2000 Subject Classification. Primary—62G32, 62PO5     

Diffusing particles with electrostatic repulsion

Summary. We study a diffusion model of an interacting particles system with general drift and diffusion coefficients, and electrostatic inter-particles repulsion. More precisely, the finite particle system is shown to be well defined thanks to recent results on multivalued stochastic differential equations (see [2]), and then we consider the behaviour of this system when the number of particles goes to infinity (through the empirical measure process). In the particular case of affine drift and constant diffusion coefficient, we prove that a limiting measure-valued process exists and is the unique solution of a deterministic PDE. Our treatment of the convergence problem (as ) is partly similar to that of T. Chan [3] and L.C.G. Rogers - Z. Shi [5], except we consider here a more general case allowing collisions between particles, which leads to a second-order limiting PDE. Received: 5 August 1996 / In revised form: 17 October 1996     

Hall sets,Lazard sets and comma-free codes

We investigate the relationship between two constructions of maximal comma-free codes described, respectively, by Eastman and by Scholtz and the notions of Hall sets and Lazard sets introduced in connection with factorizations of free monoids and bases of free Lie algebras.     

Numerical methods for the simulation of a coalescence-driven droplet size distribution

The droplet size distribution in a turbulent flow field is considered and modeled by means of a population balance system. This paper studies different numerical methods for the 4D population balance equation and their impact on an output of interest, the time-space-averaged droplet size distribution at the outlet, which is known from experiments. These methods include different interpolations of the experimental data at the inlet, various discretizations in time and space, and different schemes for computing the coalescence integrals. It will be shown that noticeable changes in the output of interest might occur. In addition, the computational efficiency of the studied methods is discussed.