Minimum deviation, quasi-LU factorization of nonsingular matrices

Not all matrices enjoy the existence of an LU factorization. For those that do not, a number of “repairs” are possible. For nonsingular matrices we offer here a permutation-free repair in which the matrix is factored , with and collectively as near as possible to lower and upper triangular (in a natural sense defined herein). Such factorization is not generally unique in any sense. In the process, we investigate further the structure of matrices without LU factorization and permutations that produce an LU factorization.     

On the primitivity of Cayley digraphs

We give a necessary and sufficient group theoretic condition for a Cayley digraph to be primitive.     

Zero-divisor graphs of amalgamated duplication of a ring along an ideal

Let R be a commutative ring with identity and let I be an ideal of R. Let R?I be the subring of R×R consisting of the elements (r,r+i) for r∈R and i∈I. We study the diameter and girth of the zero-divisor graph of the ring R?I.     

Stochastic matrices and a property of the infinite sequences of linear functionals

Our starting point is the proof of the following property of a particular class of matrices. Let T={T_i,j} be a n×m non-negative matrix such that ∑_jT_i,j=1 for each i. Suppose that for every pair of indices (i,j), there exists an index l such that T_i,l≠T_j,l. Then, there exists a real vector k=(k₁,k₂,…,k_m)^T,k_i≠k_j,i≠j;0<k_i?1, such that, if i≠j.Then, we apply that property of matrices to probability theory. Let us consider an infinite sequence of linear functionals , corresponding to an infinite sequence of probability measures {μ_(·)(i)}_i∈N, on the Borel σ-algebra such that, . The property of matrices described above allows us to construct a real bounded one-to-one piecewise continuous and continuous from the left function f such that

     

A geometric perspective on counting non-negative integer solutions and combinatorial identities

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.     

The least eigenvalue of a graph with cut vertices

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound.     

Componentwise error analysis for the block LU factorization of totally nonnegative matrices

For the first time, perturbation bounds including componentwise perturbation bounds for the block LU factorization have been provided by Dopico and Molera (2005) [5]. In this paper, componentwise error analysis is presented for computing the block LU factorization of nonsingular totally nonnegative matrices. We present a componentwise bound on the equivalent perturbation for the computed block LU factorization. Consequently, combining with the componentwise perturbation results we derive componentwise forward error bounds for the computed block factors.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

On a combinatorial problem related to permanents

Some numerical results will be presented concerning the largest and smallest values of square permanents containing the integers 1, 2, 3, ...,n ² n=1(1)8.Dedicated to Peter Naur on the occasion of his 60th birthday     

A factorization of the symmetric Pascal matrix involving the Fibonacci matrix

In this short note, we give a factorization of the Pascal matrix. This result was apparently missed by Lee et al. [Some combinatorial identities via Fibonacci numbers, Discrete Appl. Math. 130 (2003) 527-534].     

Spectrally arbitrary, nonderogatory factorization over a general field

It is known that a nonsingular, nonscalar matrix A, over the complex field, may be factored as A=BC, in which the spectra of B and C are arbitrary, subject to detBdetC=detA, and that B and C may be taken to be nonderogatory. The purpose of this paper is to establish this result over a general field with at least four elements.     

A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

Dominating sets of the comaximal and ideal-based zero-divisor graphs of commutative rings

Abstract

Let R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by Γ_I (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this paper is to study the dominating sets and domination number of Γ_I (R) and the comaximal graph CG₂(R) \ J (R) (or CGJ (R) for short) where CG₂(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R.     

On the trivectors of a 6-dimensional symplectic vector space

Let V be a 6-dimensional vector space over a field F, let f be a nondegenerate alternating bilinear form on V and let Sp(V,f)≅Sp₆(F) denote the symplectic group associated with (V,f). The group GL(V) has a natural action on the third exterior power ?³V of V and this action defines five families of nonzero trivectors of V (four of whose are orbits for any choice of F). In this paper, we divide three of these five families into orbits for the action of Sp(V,f)⊆GL(V) on ?³V.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.     

On minors of the compound matrix of a Laplacian

Let L   be an n×n$n\times n$ matrix with zero row and column sums, n?3$n?3$. We obtain a formula for any minor of the (n−2)$(n-2)$-th compound of L. An application to counting spanning trees extending a given forest is given.     

Hadwiger's conjecture forK 6-free graphs

In 1943, Hadwiger made the conjecture that every loopless graph not contractible to the complete graph ont+1 vertices ist-colourable. Whent3 this is easy, and whent=4, Wagner's theorem of 1937 shows the conjecture to be equivalent to the four-colour conjecture (the 4CC). However, whent5 it has remained open. Here we show that whent=5 it is also equivalent to the 4CC. More precisely, we show (without assuming the 4CC) that every minimal counterexample to Hadwiger's conjecture whent=5 is apex, that is, it consists of a planar graph with one additional vertex. Consequently, the 4CC implies Hadwiger's conjecture whent=5, because it implies that apex graphs are 5-colourable.Research partially supported by NSF grants number DMS 8903132, and DMS 9103480 respectively. Both authors were also partially supported by the DIMACS Center at Rutgers University, and the research was carried out partially under a consulting agreement with Bellcore.     

On a kind of curious binomial identity

As a generalization of Calkin's identity and its alternating form, we compute a kind of binomial identity involving some real number sequences and a partial sum of the binomial coefficients, from which many interesting identities follow.     

A characterization of graphs with rank 4

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4.