Sandwich semigroups in locally small categories I: foundations

Fix (not necessarily distinct) objects i and j of a locally small category S, and write \(S_{ij}\) for the set of all morphisms \(i\rightarrow j\). Fix a morphism \(a\in S_{ji}\), and define an operation \(\star _a\) on \(S_{ij}\) by \(x\star _ay=xay\) for all \(x,y\in S_{ij}\). Then \((S_{ij},\star _a)\) is a semigroup, known as a sandwich semigroup, and denoted by \(S_{ij}^a\). This article develops a general theory of sandwich semigroups in locally small categories. We begin with structural issues such as regularity, Green’s relations and stability, focusing on the relationships between these properties on \(S_{ij}^a\) and the whole category S. We then identify a natural condition on a, called sandwich regularity, under which the set \({\text {Reg}}(S_{ij}^a)\) of all regular elements of \(S_{ij}^a\) is a subsemigroup of \(S_{ij}^a\). Under this condition, we carefully analyse the structure of the semigroup \({\text {Reg}}(S_{ij}^a)\), relating it via pullback products to certain regular subsemigroups of \(S_{ii}\) and \(S_{jj}\), and to a certain regular sandwich monoid defined on a subset of \(S_{ji}\); among other things, this allows us to also describe the idempotent-generated subsemigroup \(\mathbb E(S_{ij}^a)\) of \(S_{ij}^a\). We also study combinatorial invariants such as the rank (minimal size of a generating set) of the semigroups \(S_{ij}^a\), \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\); we give lower bounds for these ranks, and in the case of \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\) show that the bounds are sharp under a certain condition we call MI-domination. Applications to concrete categories of transformations and partial transformations are given in Part II.     

Extension of the Set of Complex Hadamard Matrices of Size 8

A complex Hadamard matrix is defined as a matrix H which fulfills two conditions, \(|H_{j,k}|=1\) for all j and k and \(HH^{*}=N \mathbb {I}_N\) where \(\mathbb {I}_N\) is an identity matrix of size N. We explore the set of complex Hadamard matrices \(\mathcal {H}_N\) of size \(N=8\) and present two previously unknown structures: a one-parametric, non-affine family \(T_8^{(1)}\) of complex Hadamard matrices and a single symmetric and isolated matrix \(A_8^{(0)}\).     

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

Semigroups of rectangular matrices under a sandwich operation

Let \({\mathcal {M}}_{mn}={\mathcal {M}}_{mn}({\mathbb {F}})\) denote the set of all \(m\times n\) matrices over a field \({\mathbb {F}}\), and fix some \(n\times m\) matrix \(A\in {\mathcal {M}}_{nm}\). An associative operation \(\star \) may be defined on \({\mathcal {M}}_{mn}\) by \(X\star Y=XAY\) for all \(X,Y\in {\mathcal {M}}_{mn}\), and the resulting sandwich semigroup is denoted \({\mathcal {M}}_{mn}^A={\mathcal {M}}_{mn}^A({\mathbb {F}})\). These semigroups are closely related to Munn rings, which are fundamental tools in the representation theory of finite semigroups. We study \({\mathcal {M}}_{mn}^A\) as well as its subsemigroups \(\hbox {Reg}({\mathcal {M}}_{mn}^A)\) and \({\mathcal {E}}_{mn}^A\) (consisting of all regular elements and products of idempotents, respectively), and the ideals of \(\hbox {Reg}({\mathcal {M}}_{mn}^A)\). Among other results, we characterise the regular elements; determine Green’s relations and preorders; calculate the minimal number of matrices (or idempotent matrices, if applicable) required to generate each semigroup we consider; and classify the isomorphisms between finite sandwich semigroups \({\mathcal {M}}_{mn}^A({\mathbb {F}}_1)\) and \({\mathcal {M}}_{kl}^B({\mathbb {F}}_2)\). Along the way, we develop a general theory of sandwich semigroups in a suitably defined class of partial semigroups related to Ehresmann-style “arrows only” categories; we hope this framework will be useful in studies of sandwich semigroups in other categories. We note that all our results have applications to the variants \({\mathcal {M}}_n^A\) of the full linear monoid \({\mathcal {M}}_n\) (in the case \(m=n\)), and to certain semigroups of linear transformations of restricted range or kernel (in the case that \(\hbox {rank}(A)\) is equal to one of m, n).     

Why there is no an existence theorem for a convex polytope with prescribed directions and perimeters of the faces?

We choose some special unit vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) in \({\mathbb {R}}^3\) and denote by \({\mathscr {L}}\subset {\mathbb {R}}^5\) the set of all points \((L_1,\ldots ,L_5)\in {\mathbb {R}}^5\) with the following property: there exists a compact convex polytope \(P\subset {\mathbb {R}}^3\) such that the vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) (and no other vector) are unit outward normals to the faces of P and the perimeter of the face with the outward normal \({\mathbf {n}}_k\) is equal to \(L_k\) for all \(k=1,\ldots ,5\). Our main result reads that \({\mathscr {L}}\) is not a locally-analytic set, i.e., we prove that, for some point \((L_1,\ldots ,L_5)\in {\mathscr {L}}\), it is not possible to find a neighborhood \(U\subset {\mathbb {R}}^5\) and an analytic set \(A\subset {\mathbb {R}}^5\) such that \({\mathscr {L}}\cap U=A\cap U\). We interpret this result as an obstacle for finding an existence theorem for a compact convex polytope with prescribed directions and perimeters of the faces.     

On decomposability of Multilinear sets

We consider the Multilinear set \({\mathcal {S}}\) defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form \(y_I = \prod _{i \in I} x_i\), \(I \in {\mathcal {I}}\), where \({\mathcal {I}}\) denotes a family of subsets of \(\{1,\ldots , n\}\) of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when \({\mathcal {S}}\) is decomposable into simpler Multilinear sets \({\mathcal {S}}_j\), \(j \in J\); namely, the convex hull of \({\mathcal {S}}\) can be obtained by convexifying each \({\mathcal {S}}_j\), separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under which \({\mathcal {S}}\) is decomposable into \({\mathcal {S}}_j\), \(j \in J\), based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.     

On homogeneous hypersurfaces in $${\mathbb {C}}^3$$

We consider a family \(M_t^n\), with \(n\geqslant 2\), \(t>1\), of real hypersurfaces in a complex affine n-dimensional quadric arising in connection with the classification of homogeneous compact simply connected real-analytic hypersurfaces in  \({\mathbb {C}}^n\) due to Morimoto and Nagano. To finalize their classification, one needs to resolve the problem of the embeddability of \(M_t^n\) in  \({\mathbb {C}}^n\) for \(n=3,7\). In our earlier article we showed that \(M_t^7\) is not embeddable in  \({\mathbb {C}}^7\) for every t and that \(M_t^3\) is embeddable in  \({\mathbb {C}}^3\) for all \(1<t<1+10^{-6}\). In the present paper, we improve on the latter result by showing that the embeddability of \(M_t^3\) in fact takes place for \(1<t<\sqrt{(2+\sqrt{2})/3}\). This is achieved by analyzing the explicit totally real embedding of the sphere \(S^3\) in \({\mathbb {C}}^3\) constructed by Ahern and Rudin. For \(t\geqslant {\sqrt{(2+\sqrt{2})/3}}\), the problem of the embeddability of \(M_t^3\) remains open.     

Invariance under outer inverses

We shall use the minus partial order combined with Pierce’s decomposition to derive the class of outer inverses for idempotents, units and group invertible elements. Subsequently we show, for matrices over a field \({\mathbb {F}}\), that the triplet \(B\hat{A}C\) is invariant under all choices of outer inverses of A if and only if \(B = 0\) or \(C = 0\).     

Diagonalization of the Finite Hilbert Transform on Two Adjacent Intervals

We continue the study of stability of solving the interior problem of tomography. The starting point is the Gelfand–Graev formula, which converts the tomographic data into the finite Hilbert transform (FHT) of an unknown function f along a collection of lines. Pick one such line, call it the x-axis, and assume that the function to be reconstructed depends on a one-dimensional argument by restricting f to the x-axis. Let \(I_1\) be the interval where f is supported, and \(I_2\) be the interval where the Hilbert transform of f can be computed using the Gelfand–Graev formula. The equation to be solved is \(\left. {\mathcal {H}}_1 f=g\right| _{I_2}\), where \({\mathcal {H}}_1\) is the FHT that integrates over \(I_1\) and gives the result on \(I_2\), i.e. \({\mathcal {H}}_1: L^2(I_1)\rightarrow L^2(I_2)\). In the case of complete data, \(I_1\subset I_2\), and the classical FHT inversion formula reconstructs f in a stable fashion. In the case of interior problem (i.e., when the tomographic data are truncated), \(I_1\) is no longer a subset of \(I_2\), and the inversion problems becomes severely unstable. By using a differential operator L that commutes with \({\mathcal {H}}_1\), one can obtain the singular value decomposition of \({\mathcal {H}}_1\). Then the rate of decay of singular values of \({\mathcal {H}}_1\) is the measure of instability of finding f. Depending on the available tomographic data, different relative positions of the intervals \(I_{1,2}\) are possible. The cases when \(I_1\) and \(I_2\) are at a positive distance from each other or when they overlap have been investigated already. It was shown that in both cases the spectrum of the operator \({\mathcal {H}}_1^*{\mathcal {H}}_1\) is discrete, and the asymptotics of its eigenvalues \(\sigma _n\) as \(n\rightarrow \infty \) has been obtained. In this paper we consider the case when the intervals \(I_1=(a_1,0)\) and \(I_2=(0,a_2)\) are adjacent. Here \(a_1 < 0 < a_2\). Using recent developments in the Titchmarsh–Weyl theory, we show that the operator L corresponding to two touching intervals has only continuous spectrum and obtain two isometric transformations \(U_1\), \(U_2\), such that \(U_2{\mathcal {H}}_1 U_1^*\) is the multiplication operator with the function \(\sigma (\lambda )\), \(\lambda \ge (a_1^2+a_2^2)/8\). Here \(\lambda \) is the spectral parameter. Then we show that \(\sigma (\lambda )\rightarrow 0\) as \(\lambda \rightarrow \infty \) exponentially fast. This implies that the problem of finding f is severely ill-posed. We also obtain the leading asymptotic behavior of the kernels involved in the integral operators \(U_1\), \(U_2\) as \(\lambda \rightarrow \infty \). When the intervals are symmetric, i.e. \(-a_1=a_2\), the operators \(U_1\), \(U_2\) are obtained explicitly in terms of hypergeometric functions.     

Hyperinvariant Subspace Problem for Some Classes of Operators

An n-normal operator may be defined as an \(n \times n\) operator matrix with entries that are mutually commuting normal operators and an operator \(T \in \mathcal {B(H)}\) is quasi-nM-hyponormal (for \(n \in \mathbb {N}\)) if it is unitarily equivalent to an \(n \times n\) upper triangular operator matrix \((T_{ij})\) acting on \(\mathcal {K}^{(n)}\), where \(\mathcal {K}\) is a separable complex Hilbert space and the diagonal entries \(T_{jj}\) \((j = 1,2,\ldots , n)\) are M-hyponormal operators in \(\mathcal {B(K)}\). This is an extended notion of n-normal operators. We prove a necessary and sufficient condition for an \(n \times n\) triangular operator matrix to have Bishop’s property \((\beta )\). This leads us to study the hyperinvariant subspace problem for an \(n \times n\) triangular operator matrix.     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

Singular Values Distribution of Squares of Elliptic Random Matrices and Type B Narayana Polynomials

We consider Gaussian elliptic random matrices X of a size \(N \times N\) with parameter \(\rho \), i.e., matrices whose pairs of entries \((X_{ij}, X_{ji})\) are mutually independent Gaussian vectors with \(\mathbb {E}\,X_{ij} = 0\), \(\mathbb {E}\,X^2_{ij} = 1\) and \(\mathbb {E}\,X_{ij} X_{ji} = \rho \). We are interested in the asymptotic distribution of eigenvalues of the matrix \(W =\frac{1}{N^2} X^2 X^{*2}\). We show that this distribution is determined by its moments, and we provide a recurrence relation for these moments. We prove that the (symmetrized) asymptotic distribution is determined by its free cumulants, which are Narayana polynomials of type B:

$$\begin{aligned} c_{2n} = \sum _{k=0}^n {\left( {\begin{array}{c}n\\ k\end{array}}\right) }^2 \rho ^{2k}. \end{aligned}$$

     

Improved upper bounds for partial spreads

A partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) is a collection of \((k-1)\)-dimensional subspaces with trivial intersection. So far, the maximum size of a partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) was known for the cases \(n\equiv 0\pmod k\), \(n\equiv 1\pmod k\), and \(n\equiv 2\pmod k\) with the additional requirements \(q=2\) and \(k=3\). We completely resolve the case \(n\equiv 2\pmod k\) for the binary case \(q=2\).     

The primitive idempotents and weight distributions of irreducible constacyclic codes

Let \({\mathbb {F}}_q\) be a finite field with q elements such that \(l^v||(q^t-1)\) and \(\gcd (l,q(q-1))=1\), where l, t are primes and v is a positive integer. In this paper, we give all primitive idempotents in a ring \(\mathbb F_q[x]/\langle x^{l^m}-a\rangle \) for \(a\in {\mathbb {F}}_q^*\). Specially for \(t=2\), we give the weight distributions of all irreducible constacyclic codes and their dual codes of length \(l^m\) over \({\mathbb {F}}_q\).     

Contractive determinantal representations of stable polynomials on a matrix polyball

We show that a polynomial p with no zeros on the closure of a matrix unit polyball, a.k.a. a cartesian product of Cartan domains of type I, and such that \(p(0)=1\), admits a strictly contractive determinantal representation, i.e., \(p=\det (I-KZ_n)\), where \(n=(n_1,\ldots ,n_k)\) is a k-tuple of nonnegative integers, \(Z_n=\bigoplus _{r=1}^k(Z^{(r)}\otimes I_{n_r})\), \(Z^{(r)}=[z^{(r)}_{ij}]\) are complex matrices, p is a polynomial in the matrix entries \(z^{(r)}_{ij}\), and K is a strictly contractive matrix. This result is obtained via a noncommutative lifting and a theorem on the singularities of minimal noncommutative structured system realizations.     

Analytic sets and extension of holomorphic maps of positive codimension

Let D, \(D'\) be arbitrary domains in \({\mathbb C}^n\) and \({\mathbb C}^N\) respectively, \(1<n\le N\), both possibly unbounded and \(M \subseteq \partial D\), \(M'\subseteq \partial D'\) be open pieces of the boundaries. Suppose that \(\partial D\) is smooth real-analytic and minimal in an open neighborhood of \({\bar{M}}\) and \(\partial D'\) is smooth real-algebraic and minimal in an open neighborhood of \({\bar{M}'}\). Let \(f: D\rightarrow D'\) be a holomorphic mapping such that the cluster set \(\mathrm{cl}_{f}(M)\) does not intersect \(D'\). It is proved that if the cluster set \(\mathrm{cl}_{f}(p)\) of some point \(p\in M\) contains some point \(q\in M'\) and the graph of f extends as an analytic set to a neighborhood of \((p, q)\in {\mathbb {C}}^n \times {\mathbb C}^N\), then f extends as a holomorphic map to a dense subset of some neighborhood of p. If in addition, \(M =\partial D\), \(M'=\partial D'\) and \(M'\) is compact, then f extends holomorphically across an open dense subset of \(\partial D\).     

Heat Kernel Empirical Laws on $${\mathbb {U}}_N$$ and $${\mathbb {GL}}_N$$GLN

This paper studies the empirical laws of eigenvalues and singular values for random matrices drawn from the heat kernel measures on the unitary groups \({\mathbb {U}}_N\) and the general linear groups \({\mathbb {GL}}_N\), for \(N\in {\mathbb {N}}\). It establishes the strongest known convergence results for the empirical eigenvalues in the \({\mathbb {U}}_N\) case, and the first known almost sure convergence results for the eigenvalues and singular values in the \({\mathbb {GL}}_N\) case. The limit noncommutative distribution associated with the heat kernel measure on \({\mathbb {GL}}_N\) is identified as the projection of a flow on an infinite-dimensional polynomial space. These results are then strengthened from variance estimates to \(L^p\) estimates for even integers p.     

Computing the Permanent of (Some) Complex Matrices

We present a deterministic algorithm, which, for any given \(0< \epsilon < 1\) and an \(n \times n\) real or complex matrix \(A=\left( a_{ij}\right) \) such that \(\left| a_{ij}-1 \right| \le 0.19\) for all \(i, j\) computes the permanent of \(A\) within relative error \(\epsilon \) in \(n^{O\left( \ln n -\ln \epsilon \right) }\) time. The method can be extended to computing hafnians and multidimensional permanents.     

Linear sets in the projective line over the endomorphism ring of a finite field

Let \({{\mathrm{{PG}}}}(1,E)\) be the projective line over the endomorphism ring \( E={{\mathrm{End}}}_q({\mathbb F}_{q^t})\) of the \({\mathbb F}_q\)-vector space \({\mathbb F}_{q^t}\). As is well known, there is a bijection \(\varPsi :{{\mathrm{{PG}}}}(1,E)\rightarrow {\mathcal G}_{2t,t,q}\) with the Grassmannian of the \((t-1)\)-subspaces in \({{\mathrm{{PG}}}}(2t-1,q)\). In this paper along with any \({\mathbb F}_q\)-linear set L of rank t in \({{\mathrm{{PG}}}}(1,q^t)\), determined by a \((t-1)\)-dimensional subspace \(T^\varPsi \) of \({{\mathrm{{PG}}}}(2t-1,q)\), a subset \(L_T\) of \({{\mathrm{{PG}}}}(1,E)\) is investigated. Some properties of linear sets are expressed in terms of the projective line over the ring E. In particular, the attention is focused on the relationship between \(L_T\) and the set \(L'_T\), corresponding via \(\varPsi \) to a collection of pairwise skew \((t-1)\)-dimensional subspaces, with \(T\in L'_T\), each of which determine L. This leads among other things to a characterization of the linear sets of pseudoregulus type. It is proved that a scattered linear set L related to \(T\in {{\mathrm{{PG}}}}(1,E)\) is of pseudoregulus type if and only if there exists a projectivity \(\varphi \) of \({{\mathrm{{PG}}}}(1,E)\) such that \(L_T^\varphi =L'_T\).     

Minimization of transformed $$L_1$$ penalty: theory,difference of convex function algorithm,and robust application in compressed sensing

We study the minimization problem of a non-convex sparsity promoting penalty function, the transformed \(l_1\) (TL1), and its application in compressed sensing (CS). The TL1 penalty interpolates \(l_0\) and \(l_1\) norms through a nonnegative parameter \(a \in (0,+\infty )\), similar to \(l_p\) with \(p \in (0,1]\), and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem, and discuss the exact recovery of \(l_0\) norm minimal solution based on the null space property (NSP). We then prove the stable recovery of \(l_0\) norm minimal solution if the sensing matrix A satisfies a restricted isometry property (RIP). We formulated a normalized problem to overcome the lack of scaling property of the TL1 penalty function. For a general sensing matrix A, we show that the support set of a local minimizer corresponds to linearly independent columns of A. Next, we present difference of convex algorithms for TL1 (DCATL1) in computing TL1-regularized constrained and unconstrained problems in CS. The DCATL1 algorithm involves outer and inner loops of iterations, one time matrix inversion, repeated shrinkage operations and matrix-vector multiplications. The inner loop concerns an \(l_1\) minimization problem on which we employ the Alternating Direction Method of Multipliers. For the unconstrained problem, we prove convergence of DCATL1 to a stationary point satisfying the first order optimality condition. In numerical experiments, we identify the optimal value \(a=1\), and compare DCATL1 with other CS algorithms on two classes of sensing matrices: Gaussian random matrices and over-sampled discrete cosine transform matrices (DCT). Among existing algorithms, the iterated reweighted least squares method based on \(l_{1/2}\) norm is the best in sparse recovery for Gaussian matrices, and the DCA algorithm based on \(l_1\) minus \(l_2\) penalty is the best for over-sampled DCT matrices. We find that for both classes of sensing matrices, the performance of DCATL1 algorithm (initiated with \(l_1\) minimization) always ranks near the top (if not the top), and is the most robust choice insensitive to the conditioning of the sensing matrix A. DCATL1 is also competitive in comparison with DCA on other non-convex penalty functions commonly used in statistics with two hyperparameters.