Spectral norm of products of random and deterministic matrices

We study the spectral norm of matrices W that can be factored as W?=?BA, where A is a random matrix with independent mean zero entries and B is a fixed matrix. Under the (4?+???)th moment assumption on the entries of A, we show that the spectral norm of such an m × n matrix W is bounded by ${\sqrt{m} + \sqrt{n}}$ , which is sharp. In other words, in regard to the spectral norm, products of random and deterministic matrices behave similarly to random matrices with independent entries. This result along with the previous work of Rudelson and the author implies that the smallest singular value of a random m × n matrix with i.i.d. mean zero entries and bounded (4?+???)th moment is bounded below by ${\sqrt{m} - \sqrt{n-1}}$ with high probability.     

Group inverse for a class of 2×2 anti-triangular block matrices over skew fields

Suppose K is a skew field. Let K ^m×n denote the set of all m×n matrices over K. In this paper, we give necessary and sufficient conditions for the existence and explicit representations of the group inverses of the block matrices in the following three cases, respectively:

1. $\mathrm{rank}(S)=\mathrm{rank}(B^{\pi}A)$ ;
2. $\mathrm{rank}(S)=\mathrm{rank}(AB^{\pi})$ ;
3. $\mathrm{rank}(S)=\mathrm{rank}(B^{\pi}A)=\mathrm{rank}(AB^{\pi})$ ,

where A,B,C??K ^n×n , B ^# exists, R(B)=R(C), N(B)=N(C) and S=B ^?? AB ^?? . The paper??s conclusions generalized some related results of Zhao and Bu (Electron. J. Linear Algebra 21:63?C75, 2010).     

Representation of cyclotomic fields and their subfields

Let $\mathbb{K}$ be a finite extension of a characteristic zero field $\mathbb{F}$ . We say that a pair of n × n matrices (A,B) over $\mathbb{F}$ represents $\mathbb{K}$ if $\mathbb{K} \cong {{\mathbb{F}\left[ A \right]} \mathord{\left/ {\vphantom {{\mathbb{F}\left[ A \right]} {\left\langle B \right\rangle }}} \right. \kern-0em} {\left\langle B \right\rangle }}$ , where $\mathbb{F}\left[ A \right]$ denotes the subalgebra of $\mathbb{M}_n \left( \mathbb{F} \right)$ containing A and 〈B〉 is an ideal in $\mathbb{F}\left[ A \right]$ , generated by B. In particular, A is said to represent the field $\mathbb{K}$ if there exists an irreducible polynomial $q\left( x \right) \in \mathbb{F}\left[ x \right]$ which divides the minimal polynomial of A and $\mathbb{K} \cong {{\mathbb{F}\left[ A \right]} \mathord{\left/ {\vphantom {{\mathbb{F}\left[ A \right]} {\left\langle {q\left( A \right)} \right\rangle }}} \right. \kern-0em} {\left\langle {q\left( A \right)} \right\rangle }}$ . In this paper, we identify the smallest order circulant matrix representation for any subfield of a cyclotomic field. Furthermore, if p is a prime and $\mathbb{K}$ is a subfield of the p-th cyclotomic field, then we obtain a zero-one circulant matrix A of size p × p such that (A, J) represents $\mathbb{K}$ , where J is the matrix with all entries 1. In case, the integer n has at most two distinct prime factors, we find the smallest order 0, 1-companion matrix that represents the n-th cyclotomic field. We also find bounds on the size of such companion matrices when n has more than two prime factors.     

On the correlation functions of the characteristic polynomials of the hermitian sample covariance matrices

We consider asymptotic behavior of the correlation functions of the characteristic polynomials of the hermitian sample covariance matrices ${H_n=n^{-1}A_{m,n}^* A_{m,n}}$ , where A _m,n is a m × n complex random matrix with independent and identically distributed entries ${\mathfrak{R}a_{\alpha j}}$ and ${\mathfrak{I}a_{\alpha j}}$ . We show that for the correlation function of any even order the asymptotic behavior in the bulk and at the edge of the spectrum coincides with those for the Gaussian Unitary Ensemble up to a factor, depending only on the fourth moment of the common probability law of entries ${\mathfrak{R}a_{\alpha j}}$ , ${\mathfrak{I}a_{\alpha j}}$ , i.e., the higher moments do not contribute to the above limit.     

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.     

Automorphisms of {{\rm M_{n}}(\mathbb{D})}, Partially Ordered by Rank Subtractivity Ordering

Let \({\mathbb{D}}\) be an arbitrary division ring and \({{\rm M_{n}}(\mathbb{D})}\) be the set of all n × n matrices over \({\mathbb{D}}\) . We define the rank subtractivity or minus partial order on \({{\rm M_{n}}(\mathbb{D})}\) as defined on \({{\rm M_{n}}(\mathbb{C})}\) , i.e., \({A \leqslant B}\) iff rank(B) = rank(A) + rank(B?A). We describe the structure of maps Φ on \({{\rm M_{n}}(\mathbb{D})}\) such that \({A\leqslant B}\) iff \({\Phi(A)\leqslant \Phi(B) (A, B\in {\rm M_{n}}(\mathbb{D}) )}\) .     

Permanent Versus Determinant over a Finite Field

Let $ \mathbb{F} $ be a finite field of characteristic different from 2. We study the cardinality of sets of matrices with a given determinant or a given permanent for the set of Hermitian matrices $ {{\mathcal{H}}_n}\left( \mathbb{F} \right) $ and for the whole matrix space M _n ( $ \mathbb{F} $ ). It is known that for n = 2, there are bijective linear maps Φ on $ {{\mathcal{H}}_n}\left( \mathbb{F} \right) $ and M _n ( $ \mathbb{F} $ ) satisfying the condition per A = det Φ(A). As an application of the obtained results, we show that if n ≥ 3, then the situation is completely different and already for n = 3, there is no pair of maps (Φ, ?), where Φ is an arbitrary bijective map on matrices and ? : $ \mathbb{F} $ → $ \mathbb{F} $ is an arbitrary map such that per A = ?(det Φ(A)) for all matrices A from the spaces $ {{\mathcal{H}}_n}\left( \mathbb{F} \right) $ and M _n ( $ \mathbb{F} $ ), respectively. Moreover, for the space M _n ( $ \mathbb{F} $ ), we show that such a pair of transformations does not exist also for an arbitrary n > 3 if the field $ \mathbb{F} $ contains sufficiently many elements (depending on n). Our results are illustrated by a number of examples.     

Dissipativity of some class of uncertain systems

We consider the system $$ \dot x = A\left( \cdot \right)x + B\left( \cdot \right)u, u = S\left( \cdot \right)x, t \geqslant t_0 , $$ where A(·) ∈ ? ^n×n , B(·) ? ^n×p , and S(·) ∈ ? ^p×n . The entries of matrices A(·), B(·), and S(·) are arbitrary bounded functionals. We consider the problem of constructing a matrix H > 0 and finding relations between the entries of the matrices B(·) and S(·) such that for a given constant matrix R the inequality $$ V\left( {x\left( t \right)} \right) < V\left( {x\left( {t_0 } \right)} \right) + \int\limits_{t_0 }^t {x*\left( \tau \right)Rx\left( \tau \right)d\tau ,} $$ where V(x) = x*Hx, is satisfied. This problem is solved for the cases where matrix A(·) has p sign-definite entries on the upper part of some subdiagonal or on the lower part of some superdiagonal. It is assumed also that all entries located to the left (or to the right) of the sign-definite entries are equal to zero.     

On the Vertices of the d-Dimensional Birkhoff Polytope

Let us denote by Ω _n the Birkhoff polytope of n×n doubly stochastic matrices. As the Birkhoff–von Neumann theorem famously states, the vertex set of Ω _n coincides with the set of all n×n permutation matrices. Here we consider a higher-dimensional analog of this basic fact. Let $\varOmega^{(2)}_{n}$ be the polytope which consists of all tristochastic arrays of order n. These are n×n×n arrays with nonnegative entries in which every line sums to 1. What can be said about $\varOmega ^{(2)}_{n}$ ’s vertex set? It is well known that an order-n Latin square may be viewed as a tristochastic array where every line contains n?1 zeros and a single 1 entry. Indeed, every Latin square of order n is a vertex of $\varOmega^{(2)}_{n}$ , but as we show, such vertices constitute only a vanishingly small subset of $\varOmega^{(2)}_{n}$ ’s vertex set. More concretely, we show that the number of vertices of $\varOmega ^{(2)}_{n}$ is at least $(L_{n})^{\frac{3}{2}-o(1)}$ , where L _n is the number of order-n Latin squares. We also briefly consider similar problems concerning the polytope of n×n×n arrays where the entries in every coordinate hyperplane sum to 1, improving a result from Kravtsov (Cybern. Syst. Anal., 43(1):25–33, 2007). Several open questions are presented as well.     

Relation modules of infinite groups, II

Let F _n denote the free group of rank n and d(G) the minimal number of generators of the finitely generated group G. Suppose that R ? F _m ? G and S ? F _m ? G are presentations of G and let $\bar R$ and $\bar S$ denote the associated relation modules of G. It is well known that $\bar R \oplus (\mathbb{Z}G)^{d(G)} \cong \bar S \oplus (\mathbb{Z}G)^{d(G)}$ even though it is quite possible that . However, to the best of the author’s knowledge no examples have appeared in the literature with the property that . Our purpose here is to exhibit, for each integer k ≥ 1, a group G that has presentations as above such that . Our approach depends on the existence of nonfree stably free modules over certain commutative rings and, in particular, on the existence of certain Hurwitz-Radon systems of matrices with integer entries discovered by Geramita and Pullman. This approach was motivated by results of Adams concerning the number of orthonormal (continuous) vector fields on spheres.     

Nielsen coincidence,fixed point and root theories of n-valued maps

Let ${(\phi, \psi)}$ be an (m, n)-valued pair of maps ${\phi, \psi : X \multimap Y}$ , where ${\phi}$ is an m-valued map and ${\psi}$ is n-valued, on connected finite polyhedra. A point ${x \in X}$ is a coincidence point of ${\phi}$ and ${\psi}$ if ${\phi(x) \cap \psi(x) \neq \emptyset}$ . We define a Nielsen coincidence number ${N(\phi : \psi)}$ which is a lower bound for the number of coincidence points of all (m, n)-valued pairs of maps homotopic to ${(\phi, \psi)}$ . We calculate ${N(\phi : \psi)}$ for all (m, n)-valued pairs of maps of the circle and show that ${N(\phi : \psi)}$ is a sharp lower bound in that setting. Specifically, if ${\phi}$ is of degree a and ${\psi}$ of degree b, then ${N(\phi : \psi) = \frac{|an - bm|}{\langle m, n \rangle}}$ , where ${\langle m, n \rangle}$ is the greatest common divisor of m and n. In order to carry out the calculation, we obtain results, of independent interest, for n-valued maps of compact connected Lie groups that relate the Nielsen fixed point number of Helga Schirmer to the Nielsen root number of Michael Brown.     

Reduction of symmetric semidefinite programs using the regular \ast-representation

We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix $*$ -representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K _8,n ) ≥ 2.9299n ² ? 6n, cr(K _9,n ) ≥ 3.8676n ² ? 8n, and (for any m ≥ 9) $$\lim_{n\to\infty}\frac{{\rm cr}(K_{m,n})}{Z(m,n)}\geq 0.8594\frac{m}{m-1},$$ where Z(m,n) is the Zarankiewicz number $\lfloor\frac{1}{4}(m-1)^2\rfloor\lfloor\frac{1}{4}(n-1)^2\rfloor$ , which is the conjectured value of cr(K _m,n ). Here the best factor previously known was 0.8303 instead of 0.8594.     

ОБ ИНтЕРпОлИРОВАНИИ В кОМплЕксНОИ ОБлАст И

LetD be a simply connected domain, the boundary of which is a closed Jordan curveγ; \(\mathfrak{M} = \left\{ {z_{k, n} } \right\}\) , 0≦k≦n; n=1, 2, 3, ..., a matrix of interpolation knots, \(\mathfrak{M} \subset \Gamma ; A_c \left( {\bar D} \right)\) the space of the functions that are analytic inD and continuous on \(\bar D; \left\{ {L_n \left( {\mathfrak{M}; f, z} \right)} \right\}\) the sequence of the Lagrange interpolation polynomials. We say that a matrix \(\mathfrak{M}\) satisfies condition (B _m ), \(\mathfrak{M}\) ∈(B _m ), if for some positive integerm there exist a setB _m containingm points and a sequencen _{p p=1} ^∞ of integers such that the series \(\mathop \Sigma \limits_{p = 1}^\infty \frac{1}{{n_p }}\) diverges and for all pairsn _i ,n _j ∈{n _p } _p=1 ^∞ the set \(\left( {\bigcap\limits_{k = 0}^{n_i } {z_{k, n_i } } } \right)\bigcap {\left( {\bigcup\limits_{k = 0}^{n_j } {z_{k, n_j } } } \right)} \) is contained inB _m . The main result reads as follows. {Let D=z: ¦z¦ \(\Gamma = \partial \bar D\) and let the matrix \(\mathfrak{M} \subset \Gamma \) satisfy condition (B_m). Then there exists a function \(f \in A_c \left( {\bar D} \right)\) such that the relation $$\mathop {\lim \sup }\limits_{n \to \infty } \left| {L_n \left( {\mathfrak{M}, f, z} \right)} \right| = \infty $$ holds almost everywhere on γ.     

On Minimum Saturated Matrices

Motivated both by the work of Anstee, Griggs, and Sali on forbidden submatrices and also by the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let ${\mathcal{F}}$ be a family of k-row matrices. A matrix M is called ${\mathcal{F}}$ -admissible if M contains no submatrix ${F \in \mathcal{F}}$ (as a row and column permutation of F). A matrix M without repeated columns is ${\mathcal{F}}$ -saturated if M is ${\mathcal{F}}$ -admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat( ${n, \mathcal{F}}$ ) which is the minimal number of columns of an ${\mathcal{F}}$ -saturated matrix with n rows. We establish the estimate sat ${(n, \mathcal{F})=O(n^{k-1})}$ for any family ${\mathcal{F}}$ of k-row matrices and also compute the sat-function for a few small forbidden matrices.     

About the maximal rank of 3-tensors over the real and the complex number field

Tensor data are becoming important recently in various application fields. In this paper, we consider the maximal rank problem of 3-tensors and extend Atkinson and Stephens’ and Atkinson and Lloyd’s results over the real number field. We also prove the assertion of Atkinson and Stephens: ${{\rm max.rank}_{\mathbb{R}}(m,n,p) \leq m+\lfloor p/2\rfloor n}$ , ${{\rm max.rank}_{\mathbb{R}}(n,n,p) \leq (p+1)n/2}$ if p is even, ${{\rm max.rank}_{\mathbb{F}}(n,n,3)\leq 2n-1}$ if ${\mathbb{F}=\mathbb{C}}$ or n is odd, and ${{\rm max.rank}_{\mathbb{F}}(m,n,3)\leq m+n-1}$ if m < n where ${\mathbb{F}}$ stands for ${\mathbb{R}}$ or ${\mathbb{C}}$ .     

Degree complexity of birational maps related to matrix inversion: symmetric case

For q?≥ 3, we let ${\mathcal{S}_q}$ denote the projectivization of the set of symmetric q × q matrices with coefficients in ${\mathbb{C}}$ . We let ${I(x)=(x_{i,j})^{-1}}$ denote the matrix inverse, and we let ${J(x)=(x_{i,j}^{-1})}$ be the matrix whose entries are the reciprocals of the entries of x. We let ${K|\mathcal{S}_q=I\circ J:~\mathcal{S}_q\rightarrow \mathcal{S}_q}$ denote the restriction of the composition I ? J to ${\mathcal{S}_q}$ . This is a birational map whose properties have attracted some attention in statistical mechanics. In this paper we compute the degree complexity of ${K|\mathcal{S}_q}$ , thus confirming a conjecture of Angles d’Auriac et?al. (J Phys A Math Gen 39:3641–3654, 2006).     

Spectral Properties for Matrix Algebras

We consider Banach algebras of infinite matrices defined in terms of a weight measuring the off-diagonal decay of the matrix entries. If a given matrix $A$ is invertible as an operator on $\ell ^2$ we analyze the decay of its inverse matrix entries in the case where the matrix algebra is not inverse closed in ${\mathcal B} (\ell ^2),$ the Banach algebra of bounded operators on $\ell ^2.$ To this end we consider a condition on sequences of weights which extends the notion of GRS-condition. Finally we focus on the behavior of inverses of pseudodifferential operators whose Weyl symbols belong to weighted modulation spaces and the weights lack the GRS condition.     

Extremal problems involving isotropic sets and functions on spaces of rectangular matrices

Let \(\mathbb{M}_{m,n}\) be the linear space of real matrices of dimension m × n. A variational problem that arises quite often in applications is that of minimizing a real-valued function f on some feasible set \(\Upomega\subseteq \mathbb{M}_{m,n}.\) Matrix optimization problems of such a degree of generality are not always easy to deal with, especially if the decision variable is a high-dimensional rectangular matrix. Sometimes, it is possible to reduce the size and complexity of the matrix optimization problem in the presence of symmetry assumptions (isotropy, orthogonal invariance, etc.). This work establishes a localization result for the solutions to a class of extremal problems involving isotropic sets and functions.     

A note on maximal regular subsemigroups of the finite transformation semigroups \mathcal{T}(n,r)

Let $\mathcal{T}_{n}$ be the semigroup of all full transformations on the finite set X _n ={1,2,…,n}. For 1≤r≤n, set $\mathcal {T}(n, r)=\{ \alpha\in\mathcal{T}_{n} | \operatorname{rank}(\alpha)\leq r\}$ . In this note we show that, for 2≤r≤n?2, any maximal regular subsemigroup of the semigroup $\mathcal{T} (n,r)$ is idempotent generated, but this may not happen in the semigroup $\mathcal{T}(n, n-1)$ .     

Mutually disjoint t-designs and t-SEEDs from extremal doubly-even self-dual codes

It is known that extremal doubly-even self-dual codes of length \(n\equiv 8\) or \(0\ (\mathrm {mod}\ 24)\) yield 3- or 5-designs respectively. In this paper, by using the generator matrices of bordered double circulant doubly-even self-dual codes, we give 3-(n, k; m)-SEEDs with (n, k, m) \(\in \{(32,8,5), (56,12,9), (56,16,9), (56,24,9), (80,16,52)\}\) . With the aid of computer, we obtain 22 generator matrices of bordered double circulant doubly-even self-dual codes of length 48, which enable us to get 506 mutually disjoint 5-(48, k, \(\lambda \) ) designs for (k, \(\lambda \) )=(12, 8),(16, 1356),(20, 36176). Moreover, this implies 5-(48, k; 506)-SEEDs for \(k=12, 16, 20, 24\) .