On minimal forbidden subgraph characterizations of balanced graphs

A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1's per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced.While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses.     

Matrix semigroups—generators and relations

Some presentations for the semigroups of all 2×2 matrices and all 2×2 matrices of determinant 0 or 1 over the field GF(p) (p prime) are given. In particular, if <a, b, c‖ R> is any (semigroup) presentation for the general linear group in terms of generators $$A = \left( {\begin{array}{*{20}c} 1 & 0 \\ 1 & 1 \\ \end{array} } \right),B = \left( {\begin{array}{*{20}c} 1 & 1 \\ 0 & 1 \\ \end{array} } \right),C = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & \xi \\ \end{array} } \right),$$ where ζ is a primitive root of 1 modulop, then the presentation $$\langle a,b,c,t|R,t^2 = ct = tc = t,tba^{p - 1} t = 0,b^{\xi - 1} atb = a^{\xi - 1} tb^\xi a^{1 - \xi - 1} \rangle $$ defines the semigroup of all 2×2 matrices over GF (2,p) in terms of generatorsA, B, C and $$T = \left( {\begin{array}{*{20}c} 1 & 0 \\ 0 & 0 \\ \end{array} } \right).$$ Generating sets and ranks of various matrix semigroups are also found.     

Justification of a Malyshev-Type Formula in the Nonnormal Case

Let A be a complex matrix of order n, n ≥ 3 . We associate with A the 3n $$Q(\gamma ) = \left( {\begin{array}{*{20}c} A & {_{\gamma 1} I_n } & {_{\gamma 3} I_n } \\ 0 & A & {_{\gamma 2} I_n } \\ 0 & 0 & A \\ \end{array} } \right),$$ where γ₁, γ₂, γ₃ are scalar parameters and γ = (γ₁, γ₂, γ₃). Let σ_i, 1 ≤ i ≤ 3n, be the singular values of Q(γ), in decreasing order. Under certain assumptions on A, the authors have proved earlier that the 2-norm distance from A to the set $\mathcal{M}$ of matrices with a zero eigenvalue of multiplicity at least 3 is equal to max $$\begin{array}{*{20}c} {\max } \\ {\gamma 1,\gamma 2,\gamma 3 \in \mathbb{C}} \\ \end{array} \;^\sigma 3n - 2(Q(\gamma )).$$ Now, the justification of this formula for the distance is given for an arbitrary matrix A.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

Normal Matrices and an Extension of Malyshev's Formula

Let A be a complex matrix of order n with n ≥ 3. We associate with A the 3n × 3n matrix $Q\left( {\gamma } \right) = \left( \begin{gathered} A \gamma _1 I_n \gamma _3 I_n \\ 0 A \gamma _2 I_n \\ 0 0 A \\ \end{gathered} \right)$ where $\gamma _1 ,\gamma _2 ,\gamma _3 $ are scalar parameters and γ=(γ₁,γ₂,γ₃). Let σ_i, 1 ≤ i ≤ 3n, be the singular values of Q(γ) in the decreasing order. We prove that, for a normal matrix A, its 2-norm distance from the set $\mathcal{M}$ of matrices with a zero eigenvalue of multiplicity at least 3 is equal to $\mathop {max}\limits_{\gamma _1 ,\gamma _2 \geqslant 0,\gamma _3 \in \mathbb{C}} \sigma _{3n - 2} (Q\left( \gamma \right)).$ This fact is a refinement (for normal matrices) of Malyshev's formula for the 2-norm distance from an arbitrary n × n matrix A to the set of n × n matrices with a multiple zero eigenvalue.     

Cones and error bounds for linear iterations

Consider an ordered Banach space with a cone of positive elementsK and a norm ∥·∥. Let [a,b] denote an order-interval; under mild conditions, ifx*∈[a,b] then $$||x * - \tfrac{1}{2}(a + b)|| \leqslant \tfrac{1}{2}||b - a||.$$ This inequality is used to generate error bounds in norm, which provide on-line exit criteria, for iterations of the type $$x_r = Ax_{r - 1} + a,A = A^ + + A^ - ,$$ whereA ⁺ andA ^? are bounded linear operators, withA ⁺ K ?K andA ^? K ? ?K. Under certain conditions, the error bounds have the form $$\begin{gathered} ||x * - x_r || \leqslant ||y_r ||,y_r = (A^ + - A^ - )y_{r - 1} , \hfill \\ ||x * - x_r || \leqslant \alpha ||\nabla x_r ||, \hfill \\ ||x * - \tfrac{1}{2}(x_r + x_{r - 1} )|| \leqslant \tfrac{1}{2}||\nabla x_r ||. \hfill \\ \end{gathered} $$ These bounds can be used on iterative methods which result from proper splittings of rectangular matrices. Specific applications with respect to certain polyhedral cones are given to the classical Jacobi and Gauss-Seidel splittings.     

Weighted inequalities for fractional type operators with some homogeneous kernels

In this paper, we study integral operators of the form Tαf(x)=∫Rn|x-A1y|-α1 ··· |x-Amy|-αmf(y)dy,where Ai are certain invertible matrices, αi 0, 1 ≤ i ≤ m, α1 + ··· + αm = n-α, 0 ≤α n. For 1/q = 1/p-α/n , we obtain the Lp (Rn, wp)-Lq(Rn, wq) boundedness for weights w in A(p, q) satisfying that there exists c 0 such that w(Aix) ≤ cw(x), a.e. x ∈ Rn , 1 ≤ i ≤ m.Moreover, we obtain theappropriate weighted BMO and weak type estimates for certain weights satisfying the above inequality. We also give a Coifman type estimate for these operators.     

Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)

We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree iso(|E(G)|^1/3). The previously best enumeration, by the first author, required maximum degreeo(|E(G)|^1/4). In particular, ifk=o(n ^1/2), the number of regular graphs of degreek and ordern is asymptotically $$\frac{{(nk)!}}{{(nk/2)!2^{nk/2} (k!)^n }}\exp \left( { - \frac{{k^2 - 1}}{4} - \frac{{k^3 }}{{12n}} + 0\left( {k^2 /n} \right)} \right).$$ Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.     

Boundary value problems for complete quasi-parabolic differential equations of odd order with variable domains of operators

We prove the well-posed solvability in the strong sense of the boundary value Problems

$$\begin{gathered} ( - 1)\frac{{_m d^{2m + 1} u}}{{dt^{2m + 1} }} + \sum\limits_{k = 0}^{m - 1} {\frac{{d^{k + 1} }}{{dt^{k + 1} }}} A_{2k + 1} (t)\frac{{d^k u}}{{dt^k }} + \sum\limits_{k = 1}^m {\frac{{d^k }}{{dt^k }}} A_{2k} (t)\frac{{d^k u}}{{dt^k }} + \lambda _m A_0 (t)u = f, \hfill \\ t \in ]0,t[,\lambda _m \geqslant 1, \hfill \\ {{d^i u} \mathord{\left/ {\vphantom {{d^i u} {dt^i }}} \right. \kern-\nulldelimiterspace} {dt^i }}|_{t = 0} = {{d^j u} \mathord{\left/ {\vphantom {{d^j u} {dt^j }}} \right. \kern-\nulldelimiterspace} {dt^j }}|_{t = T} = 0,i = 0,...,m,j = 0,...,m - 1,m = 0,1,..., \hfill \\ \end{gathered} $$

where the unbounded operators A _s (t), s > 0, in a Hilbert space H have domains D(A _s (t)) depending on t, are subordinate to the powers A ^1?(s?1)/2m (t) of some self-adjoint operators A(t) ≥ 0 in H, are [(s+1)/2] times differentiable with respect to t, and satisfy some inequalities. In the space H, the maximally accretive operators A ₀(t) and the symmetric operators A _s (t), s > 0, are approximated by smooth maximally dissipative operators B(t) in such a way that

$$\begin{gathered} \mathop {lim}\limits_{\varepsilon \to 0} Re(A_0 (t)B_\varepsilon ^{ - 1} (t)(B_\varepsilon ^{ - 1} (t))^ * u,u)_H = Re(A_0 (t)u,u)_H \geqslant c(A(t)u,u)_H \hfill \\ \forall u \in D(A_0 (t)),c > 0, \hfill \\ \end{gathered} $$

, where the smoothing operators are defined by

$$B_\varepsilon ^{ - 1} (t) = (I - \varepsilon B(t))^{ - 1} ,(B_\varepsilon ^{ - 1} (t)) * = (I - \varepsilon B^ * (t))^{ - 1} ,\varepsilon > 0.$$

.

     

An example on strong shift equivalence of positive integral matrices

The following matrices are considered $$A_k = \left( {\begin{array}{*{20}c} k \\ 1 \\ \end{array} \begin{array}{*{20}c} 2 \\ k \\ \end{array} } \right), B_k \left( {\begin{array}{*{20}c} {k - 1} \\ 1 \\ \end{array} \begin{array}{*{20}c} 1 \\ {k + 1} \\ \end{array} } \right),k \in \mathbb{N},$$ which are strong shift equivalent in the sense ofWilliams [7]. In case \(k + \sqrt 2 \) is a prime number of the algebraic field \(\mathbb{Q}(\sqrt 2 )\) matrices are defined which determine the possible choices of rank two matrices connectingA _k andB _k in the sense of strong shift equivalence. A complete list of all these matrices is given.     

On the H p -L q boundedness of some fractional integral operators

Let A ₁, …, A _m be n × n real matrices such that for each 1 ? i ? m, A _i is invertible and A _i ? A _j is invertible for i ≠ j. In this paper we study integral operators of the form $$Tf(x) = \int {{k_1}(x - {A_{1y}}){k_2}(x - {A_{2y}}) \ldots {k_m}(x - {A_{my}})f(y){\rm{d}}y}$$ ${k_i}(y) = \sum\limits_{j \in z} {{2^{jn/{q_i}}}} \varphi i,j({2^j}y),1 \le {q_i} < \infty ,1/{q_1} + 1/q + ... + 1/q = 1 - r,0 \le r < 1, and \varphi i,j$ satisfying suitable regularity conditions. We obtain the boundedness of T: H ^p (? ⁿ ) → L ^q (? ⁿ ) for 0 < p < 1/r and 1/q = 1/p-r. We also show that we can not expect the H ^p -H ^q boundedness of this kind of operators.     

Fractional Type Integral Operators on Variable Hardy Spaces

Given certain n × n invertible matrices A ₁, . . . , A _m and 0 ≦ α < n, we obtain the \({H^{p(.)}(\mathbb{R}^n) \to L^{q(.)}(\mathbb{R}^n)}\) boundedness of the integral operator with kernel \({k(x, y) = |x - A_1y|^{-\alpha_1} . . . |x - A_my|^{-\alpha_m}}\) , where α ₁ +  . . . + α _m = n ? α and p(.), q(.) are exponent functions satisfying log-Hölder continuity conditions locally and at infinity related by \({\frac{1}{q(.)} = \frac{1}{p(.)} - \frac{\alpha}{n}}\) . We also obtain the \({H^{p(.)}(\mathbb{R}^n) \to H^{q(.)}(\mathbb{R}^n)}\) boundedness of the Riesz potential operator.     

On the Distance to the Closest Matrix with Triple Zero Eigenvalue

The 2-norm distance from a matrix A to the set ${\mathcal{M}}$ of n × n matrices with a zero eigenvalue of multiplicity ≥3 is estimated. If $$Q(\gamma _1 ,\gamma _2 ,\gamma _3 ) = \left( {\begin{array}{*{20}c} A &amp; {\gamma _1 I_n } &amp; {\gamma _3 I_n } \\ 0 &amp; A &amp; {\gamma _2 I_n } \\ 0 &amp; 0 &amp; A \\ \end{array} } \right), n \geqslant 3,$$ then $$\rho _2 (A,{\mathcal{M}}) \geqslant {\mathop {max}\limits_{\gamma _1 ,\gamma _2 \geqslant 0,\gamma _3 \in {\mathbb{C}}}} \sigma _{3n - 2} (Q(\gamma _1 ,\gamma _2 ,\gamma _3 )),$$ where σⁱ(·)is the ith singular value of the corresponding matrix in the decreasing order of singular values. Moreover, if the maximum on the right-hand side is attained at the point $\gamma ^ * = (\gamma _1^ * ,\gamma _2^ * ,\gamma _3^ * )$ , where $\gamma _1^ * \gamma _2^ * \ne 0$ , then, in fact, one has the exact equality $$\rho _2 (A,{\mathcal{M}}) = \sigma _{3n - 2} (Q(\gamma _1^ * ,\gamma _2^ * ,\gamma _3^ * )).$$ This result can be regarded as an extension of Malyshev's formula, which gives the 2-norm distance from A to the set of matrices with a multiple zero eigenvalue.     

Monotonicity properties of interpolation spaces

For any interpolation pair (A ₀ A ₁), Peetre’sK-functional is defined by: $$K\left( {t,a;A_0 ,A_1 } \right) = \mathop {\inf }\limits_{a = a_0 + a_1 } \left( {\left\| {a_0 } \right\|_{A_0 } + t\left\| {a_1 } \right\|_{A_1 } } \right).$$ It is known that for several important interpolation pairs (A ₀,A ₁), all the interpolation spacesA of the pair can be characterised by the property ofK-monotonicity, that is, ifa∈A andK(t, b; A₀, A₁)≦K(t, a; A₀, A₁) for all positivet thenb∈A also. We give a necessary condition for an interpolation pair to have its interpolation spaces characterized byK-monotonicity. We describe a weaker form ofK-monotonicity which holds for all the interpolation spaces of any interpolation pair and show that in a certain sense it is the strongest form of monotonicity which holds in such generality. On the other hand there exist pairs whose interpolation spaces exhibit properties lying somewhere betweenK-monotonicity and weakK-monotonicity. Finally we give an alternative proof of a result of Gunnar Sparr, that all the interpolation spaces for (L _v ^p , L _w ^q ) areK-monotone.     

Hulls of codes from incidence matrices of connected regular graphs

The hulls of codes from the row span over ${\mathbb{F}_p}$ , for any prime p, of incidence matrices of connected k-regular graphs are examined, and the dimension of the hull is given in terms of the dimension of the row span of A + kI over ${\mathbb{F}_p}$ , where A is an adjacency matrix for the graph. If p = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown by Dankelmann et al. (Des. Codes Cryptogr. 2012) that the hull is either {0} or has minimum weight at least 2k?2. Here we show that if the graph is strongly regular with parameter set (n, k, λ, μ), then, unless k is even and μ is odd, the binary hull is non-trivial, of minimum weight generally greater than 2k ? 2, and we construct words of low weight in the hull; if k is even and μ is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k ≥ 3, that has an ?-cycle for some ? ≥ 3, the binary hull is shown to be non-trivial with minimum weight at most 2?(k?2). Properties of the p-ary hulls are also established.     

The reverse order law for theW-weighted Drazin inverse of multiple matrices product

By using the rank methods of matrix, a necessary and sufficient condition is established for reverse order law $$\begin{gathered} WA_{d,W} W = (W_n (A_n )_{d,W_n } W_n )(W_{n - 1} (A_{n - 1} )_{d,W_{n - 1} } W_{n - 1} ) \hfill \\ ... (W_1 (A_1 )_{d,W_1 } W_1 ) \hfill \\ \end{gathered} $$ to hold for the W-weighted Drazin inverses, whereA =A ₁ A ₂ … A _n andW =W _n W _n-1 …W ₁. This result is the extension of the result proposed by [Linear Algebra Appl., 348(2002)265-272] and the result proposed by [J. Math. Research and Exposition. 19(1999)355-358].     

The reverse order law for {1, 3, 4}-inverse of the product of two matrices

The relationship between {1, 3, 4}-inverses of AB and the product of {1, 3, 4}-inverses of A and B have been studied in this paper. The necessary and sufficient conditions for B{1,3,4}A{1,3,4}⊆(AB){1,3,4}, B{1,3,4}A{1,3,4}⊇(AB){1,3,4} and B{1,3,4}A{1,3,4}=(AB){1,3,4} are given.     

Codes and designs from triangular graphs and their line graphs

For any prime p, we consider p-ary linear codes obtained from the span over \mathbbF_p \mathbb{F}_p _p of rows of incidence matrices of triangular graphs, differences of the rows and adjacency matrices of line graphs of triangular graphs. We determine parameters of the codes, minimum words and automorphism groups. We also show that the codes can be used for full permutation decoding.     

Expose-and-merge exploration and the chromatic number of a random graph

The expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexityn ^O(logn) is described and used to show that the chromatic number of a random graph for any edge probability 0<p<1 falls in the interval $$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$ with probability approaching unity asn→∞.     

On congruence lattices of nilsemigroups

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with \(2 \times 2\) matrices over \(\mathbb {F}_p\). Since there are many known pairs of \(2 \times 2\) matrices over \(\mathbb {Z}\) that generate a free monoid, this yields numerous pairs of matrices over \(\mathbb {F}_p\), for a sufficiently large prime p, that are candidates for collision-resistant hashing. However, this trick has a flip side, and lifting matrix entries to \(\mathbb {Z}\) may facilitate finding a collision. This “lifting attack” was successfully used by Tillich and Zémor in the special case where two matrices A and B generate (as a monoid) the whole monoid \(SL_2(\mathbb {Z}_+)\). However, in this paper we show that the situation with other, “similar”, pairs of matrices from \(SL_2(\mathbb {Z})\) is different, and the “lifting attack” can (in some cases) produce collisions in the group generated by A and B, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from \(SL_2(\mathbb {F}_p)\).