On the bilinearity rank of a proper cone and Lyapunov-like transformations

A real square matrix \(Q\) is a bilinear complementarity relation on a proper cone \(K\) in \(\mathbb{R }^n\) if $$\begin{aligned} x\in K, s\in K^*,\,\,\text{ and }\,\,\langle x,s\rangle =0\Rightarrow x^{T}Qs=0, \end{aligned}$$ where \(K^*\) is the dual of \(K\) . The bilinearity rank of \(K\) is the dimension of the linear space of all bilinear complementarity relations on \(K\) . In this article, we continue the study initiated by Rudolf et al. (Math Prog Ser B 129:5–31, 2011). We show that bilinear complementarity relations are related to Lyapunov-like transformations that appear in dynamical systems and in complementarity theory and further show that the bilinearity rank of \(K\) is the dimension of the Lie algebra of the automorphism group of \(K\) . In addition, we correct a result of Rudolf et al., compute the bilinearity ranks of symmetric and completely positive cones, and state some Schur-type results for Lyapunov-like transformations.     

Tensor Rank: Matching Polynomials and Schur Rings

We study the polynomial equations vanishing on tensors of a given rank. By means of polarization we reduce them to elements  $A$ of the group algebra ${\mathbb {Q}}[S_n\times S_n]$ and describe explicit linear equations on the coefficients of  $A$ to vanish on tensors of a given rank. Further, we reduce the study to the Schur ring over the group $S_n\times S_n$ that arises from the diagonal conjugacy action of  $S_n$ . More closely, we consider elements of ${\mathbb {Q}}[S_n\times S_n]$ vanishing on tensors of rank $n-1$ and describe them in terms of triples of Young diagrams, their irreducible characters, and nonvanishing of their Kronecker coefficients. Also, we construct a family of elements in ${\mathbb {Q}}[S_n\times S_n]$ vanishing on tensors of rank $n-1$ and illustrate our approach by a sharp lower bound on the border rank of an explicitly produced tensor. Finally, we apply this construction to prove a lower bound $5n^2/4$ on the border rank of the matrix multiplication tensor (being, of course, weaker than the best known one $(2-\epsilon )\cdot n^2$ , due to Landsberg, Ottaviani).     

Determinantal representations of the generalized inverses A_{T,S}^{(2)} over the quaternion skew field with applications

We first present some determinantal representations of one {1,5}-inverse of a quaternion matrix within the framework of a theory of the row and column determinants. As applications, we show some new explicit expressions of generalized inverses $A_{r_{T_{1}, S_{1}}}^{( 2)}$ , $A_{l_{T_{2},S_{2}}}^{(2)}$ and $A_{_{( T_{1},T_{2}) , ( S_{1},S_{2}) }}^{( 2) }$ over the quaternion skew field. Finally, we give the representations of the unique solution to some restricted left and right systems of quaternionic linear equations. The findings of this paper extend some known results in the literature.     

Discontinuous Galerkin method for hyperbolic equations involving \delta -singularities: negative-order norm error estimates and applications

In this paper, we develop and analyze discontinuous Galerkin (DG) methods to solve hyperbolic equations involving $\delta $ -singularities. Negative-order norm error estimates for the accuracy of DG approximations to $\delta $ -singularities are investigated. We first consider linear hyperbolic conservation laws in one space dimension with singular initial data. We prove that, by using piecewise $k$ th degree polynomials, at time $t$ , the error in the $H^{-(k+2)}$ norm over the whole domain is $(k+1/2)$ th order, and the error in the $H^{-(k+1)}(\mathbb R \backslash \mathcal R _t)$ norm is $(2k+1)$ th order, where $\mathcal R _t$ is the pollution region due to the initial singularity with the width of order $\mathcal O (h^{1/2} \log (1/h))$ and $h$ is the maximum cell length. As an application of the negative-order norm error estimates, we convolve the numerical solution with a suitable kernel which is a linear combination of B-splines, to obtain $L^2$ error estimate of $(2k+1)$ th order for the post-processed solution. Moreover, we also obtain high order superconvergence error estimates for linear hyperbolic conservation laws with singular source terms by applying Duhamel’s principle. Numerical examples including an acoustic equation and the nonlinear rendez-vous algorithms are given to demonstrate the good performance of DG methods for solving hyperbolic equations involving $\delta $ -singularities.     

Large-scale Stein and Lyapunov equations, Smith method, and applications

We consider the solution of large-scale Lyapunov and Stein equations. For Stein equations, the well-known Smith method will be adapted, with $A_k = A^{2^k}$ not explicitly computed but in the recursive form $A_k = A_{k-1}^{2}$ , and the fast growing but diminishing components in the approximate solutions truncated. Lyapunov equations will be first treated with the Cayley transform before the Smith method is applied. For algebraic equations with numerically low-ranked solutions of dimension n, the resulting algorithms are of an efficient O(n) computational complexity and memory requirement per iteration and converge essentially quadratically. An application in the estimation of a lower bound of the condition number for continuous-time algebraic Riccati equations is presented, as well as some numerical results.     

Bott-Duffin inverse over the quaternion skew field with applications

In this paper, we show some properties of the Bott-Duffin inverses $A_{r_{ ( L_{1} ) }}^{ ( -1 ) }$ and $A_{l_{ ( L_{2} ) }}^{ ( -1 ) }$ over the quaternion skew field. In particular, we establish the determinantal representations of these generalized inverses by the theory of the column and row determinants. Moreover, we derive some Cramer rules for the unique solution to some restricted linear quaternion equations. The findings of this paper extend some known results in the literature.     

An error estimate for the finite difference approximation to degenerate convection–diffusion equations

We consider semi-discrete first-order finite difference schemes for a nonlinear degenerate convection?Cdiffusion equations in one space dimension, and prove an L ¹ error estimate. Precisely, we show that the ${L^1_{\rm{loc}}}$ difference between the approximate solution and the unique entropy solution converges at a rate ${\mathcal{O}(\Delta x^{1/11})}$ , where ${\Delta x}$ is the spatial mesh size. If the diffusion is linear, we get the convergence rate ${\mathcal{O}(\Delta x^{1/2})}$ , the point being that the ${\mathcal{O}}$ is independent of the size of the diffusion.     

A variable fixing version of the two-block nonlinear constrained Gauss–Seidel algorithm for \ell _1-regularized least-squares

The problem of finding sparse solutions to underdetermined systems of linear equations is very common in many fields as e.g. signal/image processing and statistics. A standard tool for dealing with sparse recovery is the \(\ell _1\) -regularized least-squares approach that has recently attracted the attention of many researchers. In this paper, we describe a new version of the two-block nonlinear constrained Gauss–Seidel algorithm for solving \(\ell _1\) -regularized least-squares that at each step of the iteration process fixes some variables to zero according to a simple active-set strategy. We prove the global convergence of the new algorithm and we show its efficiency reporting the results of some preliminary numerical experiments.     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

Orthogonality Principle for Bilinear Littlewood–Paley Decompositions

We explore Littlewood–Paley like decompositions of bilinear Fourier multipliers. Grafakos and Li (Am. J. Math. 128(1):91–119 2006) showed that a bilinear symbol supported in an angle in the positive quadrant is bounded from \(L^p\times L^q\) into \(L^r\) if its restrictions to dyadic annuli are bounded bilinear multipliers in the local \(L^2\) case \(p\ge 2\) , \(q\ge 2\) , \(r= 1/(p^{-1}+q^{-1})\le 2\) . We show that this range of indices is sharp and also discuss similar results for multipliers supported near axis and negative diagonal.     

A remark on Schröder’s equation: formal and analytic linearization of iterative roots of the power series f(z)=z

We study Schröder’s equation (i.e. the problem of linearization) for local analytic functions \(F\) with \(F(0)=0, F'(0) \ne 1, F'(0)\) a root of \(1\) . While Schröder’s equation in this case need not have even a formal solution, we show that if \(F\) is formally linearizable, then it can also be linearized by an invertible local analytic transformation. On the other hand, there exist also divergent series solutions of Schröder’s equation in this situation. We give some applications of our results to iterative functional equations, functional-differential equations and iteration groups.     

Bilinear Forms and Fierz Identities for Real Spin Representations

Given a real representation of the Clifford algebra corresponding to ${\mathbb{R}^{p+q}}$ with metric of signature (p, q), we demonstrate the existence of two natural bilinear forms on the space of spinors. With the Clifford action of k-forms on spinors, the bilinear forms allow us to relate two spinors with elements of the exterior algebra. From manipulations of a rank four spinorial tensor introduced in [1], we are able to find a general class of identities which, upon specializing from four spinors to two spinors and one spinor in signatures (1,3) and (10,1), yield some well-known Fierz identities. We will see, surprisingly, that the identities we construct are partly encoded in certain involutory real matrices that resemble the Krawtchouk matrices [2][3].     

Degenerations to unobstructed Fano Stanley–Reisner schemes

We construct degenerations of Mukai varieties and linear sections thereof to special unobstructed Fano Stanley–Reisner schemes corresponding to convex deltahedra. This can be used to find toric degenerations of rank one index one Fano threefolds. Furthermore, we show that the Stanley–Reisner ring of the boundary complex of the dual polytope of the associahedron has trivial \(T^2\) . This can be used to find new toric degenerations of linear sections of \(G(2,n)\) .     

The extremal solution for the fractional Laplacian

We study the extremal solution for the problem \((-\Delta )^s u=\lambda f(u)\) in \(\Omega \) , \(u\equiv 0\) in \(\mathbb R ^n\setminus \Omega \) , where \(\lambda >0\) is a parameter and \(s\in (0,1)\) . We extend some well known results for the extremal solution when the operator is the Laplacian to this nonlocal case. For general convex nonlinearities we prove that the extremal solution is bounded in dimensions \(n<4s\) . We also show that, for exponential and power-like nonlinearities, the extremal solution is bounded whenever \(n<10s\) . In the limit \(s\uparrow 1\) , \(n<10\) is optimal. In addition, we show that the extremal solution is \(H^s(\mathbb R ^n)\) in any dimension whenever the domain is convex. To obtain some of these results we need \(L^q\) estimates for solutions to the linear Dirichlet problem for the fractional Laplacian with \(L^p\) data. We prove optimal \(L^q\) and \(C^\beta \) estimates, depending on the value of \(p\) . These estimates follow from classical embedding results for the Riesz potential in \(\mathbb R ^n\) . Finally, to prove the \(H^s\) regularity of the extremal solution we need an \(L^\infty \) estimate near the boundary of convex domains, which we obtain via the moving planes method. For it, we use a maximum principle in small domains for integro-differential operators with decreasing kernels.     

High rank elliptic curves with prescribed torsion group over quadratic fields

There are 26 possibilities for the torsion groups of elliptic curves defined over quadratic number fields. We present examples of high rank elliptic curves with a given torsion group which set the current rank records for most of the torsion groups. In particular, we show that for each possible torsion group, except maybe for \(\mathbb {Z}/15\mathbb {Z}\) , there exists an elliptic curve over some quadratic field with this torsion group and with rank \(\ge 2\) .     

Polytopes of Minimum Positive Semidefinite Rank

The positive semidefinite (psd) rank of a polytope is the smallest $k$ k for which the cone of $k \times k$ k × k real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, and we characterize those polytopes whose psd rank equals this lower bound. We give several classes of polytopes that achieve the minimum possible psd rank including a complete characterization in dimensions two and three.     

On a Priori Energy Estimates for Characteristic Boundary Value Problems

Motivated by the study of certain non linear free-boundary value problems for hyperbolic systems of partial differential equations arising in Magneto-Hydrodynamics, in this paper we show that an a priori estimate of the solution to certain boundary value problems, in the conormal Sobolev space \(H^1_{ tan}\) , can be transformed into an \(L^2\) a priori estimate of the same problem.     

Character formulæ and GKRS multiplets in equivariant K-theory

Let $G$ be a compact Lie group, $H$ a closed subgroup of maximal rank and $X$ a topological $G$ -space. We obtain a variety of results concerning the structure of the $H$ -equivariant K-ring $K_H^*(X)$ viewed as a module over the $G$ -equivariant K-ring $K_G^*(X)$ . One result is that the module has a nonsingular bilinear pairing; another is that the module contains multiplets which are analogous to the Gross–Kostant–Ramond–Sternberg multiplets of representation theory.     

New results and applications for multi-secret sharing schemes

In a multi-secret sharing scheme (MSSS), \(\ell \) different secrets are distributed among the players in some set \(\mathcal{P }=\{P_1,\ldots ,P_n\}\) , each one according to an access structure. The trivial solution to this problem is to run \(\ell \) independent instances of a standard secret sharing scheme, one for each secret. In this solution, the length of the secret share to be stored by each player grows linearly with \(\ell \) (when keeping all other parameters fixed). Multi-secret sharing schemes have been studied by the cryptographic community mostly from a theoretical perspective: different models and definitions have been proposed, for both unconditional (information-theoretic) and computational security. In the case of unconditional security, there are two different definitions. It has been proved that, for some particular cases of access structures that include the threshold case, a MSSS with the strongest level of unconditional security must have shares with length linear in \(\ell \) . Therefore, the optimal solution in this case is equivalent to the trivial one. In this work we prove that, even for a more relaxed notion of unconditional security, and for some kinds of access structures (in particular, threshold ones), we have the same efficiency problem: the length of each secret share must grow linearly with \(\ell \) . Since we want more efficient solutions, we move to the scenario of MSSSs with computational security. We propose a new MSSS, where each secret share has constant length (just one element), and we formally prove its computational security in the random oracle model. To the best of our knowledge, this is the first formal analysis on the computational security of a MSSS. We show the utility of the new MSSS by using it as a key ingredient in the design of two schemes for two new functionalities: multi-policy signatures and multi-policy decryption. We prove the security of these two new multi-policy cryptosystems in a formal security model. The two new primitives provide similar functionalities as attribute-based cryptosystems, with some advantages and some drawbacks that we discuss at the end of this work.