On Compact Wavelet Matrices of Rank m and of Order and Degree N

A new parametrization (one-to-one onto map) of compact wavelet matrices of rank $m$ and of order and degree $N$ is proposed in terms of coordinates in the Euclidian space $\mathbb {C}^{(m-1)N}$ . The developed method depends on Wiener–Hopf factorization of corresponding unitary matrix functions and allows to construct compact wavelet matrices efficiently. Some applications of the proposed method are discussed.     

The polynomial dual of an operator ideal

We prove that the adjoint of a continuous homogeneous polynomial $P$ between Banach spaces belongs to a given operator ideal $\mathcal I$ if and only if $P$ admits a factorization $P = u \circ Q$ where the adjoint of the linear operator $u$ belongs to $\mathcal I$ . Several consequences of this factorization are obtained, for example we characterize the polynomials whose adjoints are absolutely $p$ -summing.     

Reorthogonalization for the Golub–Kahan–Lanczos bidiagonal reduction

The Golub–Kahan–Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of $X \in \mathbb{R }^{m \times n}, m \ge n$ , given by $$\begin{aligned} X = UBV^T \end{aligned}$$ where $U \in \mathbb{R }^{m \times n}$ is left orthogonal, $V \in \mathbb{R }^{n \times n}$ is orthogonal, and $B \in \mathbb{R }^{n \times n}$ is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of $U$ and $V$ tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257–2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices $U$ and $V$ is shown to be very effective by the results presented here. Supposing that $V$ is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q–R factorization of $\left( \begin{array}{c} 0_{n \times k} \\ X V_k \end{array}\right) $ where $V_k = V(:,1:k)$ . That model is used to show that if $\varepsilon _M $ is the machine unit and $$\begin{aligned} \bar{\eta }= \Vert \mathbf{tril }(I-V^T\!~V)\Vert _F, \end{aligned}$$ where $\mathbf{tril }(\cdot )$ is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix $X + \delta X$ , $\Vert \delta X\Vert _F = \mathcal O (\varepsilon _M + \bar{\eta }) \Vert X\Vert _F$ ; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.     

Reorthogonalized block classical Gram–Schmidt

A reorthogonalized block classical Gram–Schmidt algorithm is proposed that factors a full column rank matrix $A$ into $A=QR$ where $Q$ is left orthogonal (has orthonormal columns) and $R$ is upper triangular and nonsingular. This block Gram–Schmidt algorithm can be implemented using matrix–matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram–Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of $R$ , the algorithm, when implemented in floating point arithmetic with machine unit $\varepsilon _M$ , produces $Q$ and $R$ such that $\Vert I- Q ^T\!~ Q \Vert =O(\varepsilon _M)$ and $\Vert A-QR \Vert =O(\varepsilon _M\Vert A \Vert )$ . The first of these bounds has not been shown for a block Gram–Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87–100, 2005) for the CGS2 algorithm.     

On the non-existence of maximal difference matrices of deficiency 1

A \(k\times u\lambda \) matrix \(M=[d_{ij}]\) with entries from a group \(U\) of order \(u\) is called a \((u,k,\lambda )\) -difference matrix over \(U\) if the list of quotients \(d_{i\ell }{d_{j\ell }}^{-1}, 1 \le \ell \le u\lambda ,\) contains each element of \(U\) exactly \(\lambda \) times for all \(i\ne j.\) Jungnickel has shown that \(k \le u\lambda \) and it is conjectured that the equality holds only if \(U\) is a \(p\) -group for a prime \(p.\) On the other hand, Winterhof has shown that some known results on the non-existence of \((u,u\lambda ,\lambda )\) -difference matrices are extended to \((u,u\lambda -1,\lambda )\) -difference matrices. This fact suggests us that there is a close connection between these two cases. In this article we show that any \((u,u\lambda -1,\lambda )\) -difference matrix over an abelian \(p\) -group can be extended to a \((u,u\lambda ,\lambda )\) -difference matrix.     

A construction of integer-valued polynomials with prescribed sets of lengths of factorizations

For an arbitrary finite non-empty set $S$ of natural numbers greater $1$ , we construct $f\in \text{ Int }(\mathbb{Z })=\{g\in \mathbb{Q }[x]\mid g(\mathbb{Z })\subseteq \mathbb{Z }\}$ such that $S$ is the set of lengths of $f$ , i.e., the set of all $n$ such that $f$ has a factorization as a product of $n$ irreducibles in $\text{ Int }(\mathbb{Z })$ . More generally, we can realize any finite non-empty multi-set of natural numbers greater 1 as the multi-set of lengths of the essentially different factorizations of $f$ .     

Proper circulant weighing matrices of weight p^2

A circulant weighing matrix \(CW(v,n)\) is a circulant matrix \(M\) of order \(v\) with \(0,\pm 1\) entries such that \(MM^T=nI_v\) . In this paper, we study proper circulant matrices with \(n=p^2\) where \(p\) is an odd prime divisor of \(v\) . For \(p\ge 5\) , it turns out that to search for such circulant matrices leads us to two group ring equations and by studying these two equations, we manage to prove that no proper \(CW(pw,p^2)\) exists when \(p\equiv 3\pmod {4}\) or \(p=5\) .     

Composed products and factors of cyclotomic polynomials over finite fields

Let q = p ^s be a power of a prime number p and let ${\mathbb {F}_{\rm q}}$ be a finite field with q elements. This paper aims to demonstrate the utility and relation of composed products to other areas such as the factorization of cyclotomic polynomials, construction of irreducible polynomials, and linear recurrence sequences over ${\mathbb {F}_{\rm q}}$ . In particular we obtain the explicit factorization of the cyclotomic polynomial ${\Phi_{2^nr}}$ over ${\mathbb {F}_{\rm q}}$ where both r ≥ 3 and q are odd, gcd(q, r) = 1, and ${n\in \mathbb{N}}$ . Previously, only the special cases when r = 1, 3, 5, had been achieved. For this we make the assumption that the explicit factorization of ${\Phi_r}$ over ${\mathbb {F}_{\rm q}}$ is given to us as a known. Let ${n = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}}$ be the factorization of ${n \in \mathbb{N}}$ into powers of distinct primes p _i , 1 ≤ i ≤ s. In the case that the multiplicative orders of q modulo all these prime powers ${p_i^{e_i}}$ are pairwise coprime, we show how to obtain the explicit factors of ${\Phi_{n}}$ from the factors of each ${\Phi_{p_i^{e_i}}}$ . We also demonstrate how to obtain the factorization of ${\Phi_{mn}}$ from the factorization of ${\Phi_n}$ when q is a primitive root modulo m and ${{\rm gcd}(m, n) = {\rm gcd}(\phi(m),{\rm ord}_n(q)) = 1.}$ Here ${\phi}$ is the Euler’s totient function, and ord _n (q) denotes the multiplicative order of q modulo n. Moreover, we present the construction of a new class of irreducible polynomials over ${\mathbb {F}_{\rm q}}$ and generalize a result due to Varshamov (Soviet Math Dokl 29:334–336, 1984).     

Asymptotics for Hessenberg Matrices for the Bergman Shift Operator on Jordan Regions

Let $G$ be a bounded Jordan domain in the complex plane. The Bergman polynomials $\{p_n\}_{n=0}^\infty $ of $G$ are the orthonormal polynomials with respect to the area measure over $G$ . They are uniquely defined by the entries of an infinite upper Hessenberg matrix $M$ . This matrix represents the Bergman shift operator of $G$ . The main purpose of the paper is to describe and analyze a close relation between $M$ and the Toeplitz matrix with symbol the normalized conformal map of the exterior of the unit circle onto the complement of $\overline{G}$ . Our results are based on the strong asymptotics of $p_n$ . As an application, we describe and analyze an algorithm for recovering the shape of $G$ from its area moments.     

Forbidden configurations and Steiner designs

Let ${\mathcal{F}}$ be a (0, 1) matrix. A (0, 1) matrix ${\mathcal{M}}$ is said to have ${\mathcal{F}}$ as a configuration if there is a submatrix of ${\mathcal{M}}$ which is a row and column permutation of ${\mathcal{F}}$ . We say that a matrix ${\mathcal{M}}$ is simple if it has no repeated columns. For a given ${v \in \mathbb{N}}$ , we shall denote by forb ${(v, \mathcal{F})}$ the maximum number of columns in a simple (0, 1) matrix with v rows for which ${\mathcal{F}}$ does not occur as a configuration. We say that a matrix ${\mathcal{M}}$ is maximal for ${\mathcal{F}}$ if ${\mathcal{M}}$ has forb ${(v, \mathcal{F})}$ columns. In this paper we show that for certain natural choices of ${\mathcal{F}}$ , forb ${(v, \mathcal{F})\leq\frac{\binom{v}{t}}{t+1}}$ . In particular this gives an extremal characterization for Steiner t-designs as maximal (0, 1) matrices in terms of certain forbidden configurations.     

Remark on the Helmholtz decomposition in domains with noncompact boundary

Let \(\varOmega \) be a domain in \(\mathbb {R}^{d+1}\) whose boundary is given as a uniform Lipschitz graph \(x_{d+1}=\eta (x)\) for \(x \in \mathbb {R}^d\) . For such a domain, it is known that the Helmholtz decomposition is not always valid in \(L^p(\varOmega )\) except for the energy space \(L^2 (\varOmega )\) . In this paper we show that the Helmholtz decomposition still holds in certain anisotropic spaces which include vector fields decaying slowly in the \(x_{d+1}\) variable. In particular, these classes include some infinite energy vector fields. For the purpose, we develop a new approach based on a factorization of divergence form elliptic operators whose coefficients are independent of one variable.     

Minimal subgroups and the structure of finite groups

A subgroup $H$ of a finite group $G$ is weakly-supplemented in $G$ if there exists a proper subgroup $K$ of $G$ such that $G=HK$ . In this paper we prove that a finite group $G$ is $p$ -nilpotent if every minimal subgroup of $P\bigcap G^{N}$ is weakly-supplemented in $G$ , and when $p=2$ either every cyclic subgroup of $P\bigcap G^{N}$ with order 4 is weakly-supplemented in $G$ or $P$ is quaternion-free, where $p$ is the smallest prime number dividing the order of $G$ , $P$ a sylow $p$ -subgroup of $G$ .     

On generalizing transitivity, persistence, and sensitivity

A subgroup property $\alpha $ is transitive in a group $G$ if $U \alpha V$ and $V \alpha G$ imply that $U \alpha G$ whenever $U \le V \le G$ , and $\alpha $ is persistent in $G$ if $U \alpha G$ implies that $U \alpha V$ whenever $U \le V \le G$ . Even though a subgroup property $\alpha $ may be neither transitive nor persistent, a given subgroup $U$ may have the property that each $\alpha $ -subgroup of $U$ is an $\alpha $ -subgroup of $G$ , or that each $\alpha $ -subgroup of $G$ in $U$ is an $\alpha $ -subgroup of $U$ . We call these subgroup properties $\alpha $ -transitivity and $\alpha $ -persistence, respectively. We introduce and develop the notions of $\alpha $ -transitivity and $\alpha $ -persistence, and we establish how the former property is related to $\alpha $ -sensitivity. In order to demonstrate how these concepts can be used, we apply the results to the cases in which $\alpha $ is replaced with “normal” and the “cover-avoidance property.” We also suggest ways in which the theory can be developed further.     

On the rank of incidence matrices in projective Hjelmslev spaces

Let \(R\) be a finite chain ring with \(|R|=q^m\) , \(R/{{\mathrm{Rad}}}R\cong \mathbb {F}_q\) , and let \(\Omega ={{\mathrm{PHG}}}({}_RR^n)\) . Let \(\tau =(\tau _1,\ldots ,\tau _n)\) be an integer sequence satisfying \(m=\tau _1\ge \tau _2\ge \cdots \ge \tau _n\ge 0\) . We consider the incidence matrix of all shape \(\varvec{m}^s=(\underbrace{m,\ldots ,m}_s)\) versus all shape \(\tau \) subspaces of \(\Omega \) with \(\varvec{m}^s\preceq \tau \preceq \varvec{m}^{n-s}\) . We prove that the rank of \(M_{\varvec{m}^s,\tau }(\Omega )\) over \(\mathbb {Q}\) is equal to the number of shape \(\varvec{m}^s\) subspaces. This is a partial analog of Kantor’s result about the rank of the incidence matrix of all \(s\) dimensional versus all \(t\) dimensional subspaces of \({{\mathrm{PG}}}(n,q)\) . We construct an example for shapes \(\sigma \) and \(\tau \) for which the rank of \(M_{\sigma ,\tau }(\Omega )\) is not maximal.     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

Prefactorized subgroups in pairwise mutually permutable products

We continue here our study of pairwise mutually and pairwise totally permutable products. We are looking for subgroups of the product in which the given factorization induces a factorization of the subgroup. In the case of soluble groups, it is shown that a prefactorized Carter subgroup and a prefactorized system normalizer exist. A less stringent property have ${\mathcal {F}}$ -residual, ${\mathcal F}$ -projector and ${\mathcal {F}}$ -normalizer for any saturated formation ${\mathcal {F}}$ including the supersoluble groups.     

Norm-Constrained Determinantal Representations of Multivariable Polynomials

For every multivariable polynomial $p$ , with $p(0)=1$ , we construct a determinantal representation, $ p=\det (I - K Z )$ , where $Z$ is a diagonal matrix with coordinate variables on the diagonal and $K$ is a complex square matrix. Such a representation is equivalent to the existence of $K$ whose principal minors satisfy certain linear relations. When norm constraints on $K$ are imposed, we give connections to the multivariable von Neumann inequality, Agler denominators, and stability. We show that if a multivariable polynomial $q$ , $q(0)=0,$ satisfies the von Neumann inequality, then $1-q$ admits a determinantal representation with $K$ a contraction. On the other hand, every determinantal representation with a contractive $K$ gives rise to a rational inner function in the Schur–Agler class.     

Wild quotient singularities of surfaces

Let $(B,\mathcal{M }_B)$ be a noetherian regular local ring of dimension $2$ with residue field $B/\mathcal{M }_B$ of characteristic $p>0$ . Assume that $B$ is endowed with an action of a finite cyclic group $H$ whose order is divisible by $p$ . Associated with a resolution of singularities of $\mathrm{Spec}B^H$ is a resolution graph $G$ and an intersection matrix $N$ . We prove in this article three structural properties of wild quotient singularities, which suggest that in general, one should expect when $H= \mathbb{Z }/p\mathbb{Z }$ that the graph $G$ is a tree, that the Smith group $\mathbb{Z }^n/\mathrm{Im}(N)$ is killed by $p$ , and that the fundamental cycle $Z$ has self-intersection $|Z^2|\le p$ . We undertake a combinatorial study of intersection matrices $N$ with a view towards the explicit determination of the invariants $\mathbb{Z }^n/\mathrm{Im}(N)$ and $Z$ . We also exhibit explicitly the resolution graphs of an infinite set of wild $\mathbb{Z }/2\mathbb{Z }$ -singularities, using some results on elliptic curves with potentially good ordinary reduction which could be of independent interest.     

Modular Decomposition of the Orlik-Terao Algebra

Let ${\mathcal{A}}$ be a collection of n linear hyperplanes in ${\mathbb{k}^\ell}$ , where ${\mathbb{k}}$ is an algebraically closed field. The Orlik-Terao algebra of ${\mathcal{A}}$ is the subalgebra ${{\rm R}(\mathcal{A})}$ of the rational functions generated by reciprocals of linear forms vanishing on hyperplanes of ${\mathcal{A}}$ . It determines an irreducible subvariety ${Y (\mathcal{A})}$ of ${\mathbb{P}^{n-1}}$ . We show that a flat X of ${\mathcal{A}}$ is modular if and only if ${{\rm R}(\mathcal{A})}$ is a split extension of the Orlik-Terao algebra of the subarrangement ${\mathcal{A}_X}$ . This provides another refinement of Stanley’s modular factorization theorem [34] and a new characterization of modularity, similar in spirit to the fibration theorem of [27]. We deduce that if ${\mathcal{A}}$ is supersolvable, then its Orlik-Terao algebra is Koszul. In certain cases, the algebra is also a complete intersection, and we characterize when this happens.     

Minimum total coloring of planar graph

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of “total coloring”. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of \(G\) is the minimum number of disjoint vertex independent sets covering a total graph of \(G\) . Here, let \(G\) be a planar graph with \(\varDelta \ge 8\) . We proved that if for every vertex \(v\in V\) , there exists two integers \(i_{v},j_{v} \in \{3,4,5,6,7,8\}\) such that \(v\) is not incident with intersecting \(i_v\) -cycles and \(j_v\) -cycles, then the vertex chromatic number of total graph of \(G\) is \(\varDelta +1\) , i.e., the total chromatic number of \(G\) is \(\varDelta +1\) .