|
Linear Algebra and its Applications
Journal Prestige (SJR): 0.994  Citation Impact (citeScore): 1 Number of Followers: 22  Subscription journalISSN (Print) 0024-3795 Published by Elsevier  [3181 journals]
|
- On higher order selfadjoint operators
- Abstract: Publication date: Available online 15 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Maryam Salehi, Karim Hedayatian For a positive integer m and a Hilbert space H an operator T in B(H), the space of all bounded linear operators on H, is called m-selfadjoint if ∑k=0m(−1)k(mk)T⁎kTm−k=0. In this paper, we show that if T∈B(H) and the spectrum of T consists of a finite number of points then it is m-selfadjoint if and only if it is an n-Jordan operator for some integer n. Moreover, we prove that if T is m-selfadjoint then T is nilpotent when it is quasinilpotent. Then we characterize m-selfadjoint weighted shift operators. Also, we show that if T is m-selfadjoint then so is p(T) when p(z) is a polynomial with real coefficients. After that, we investigate an elementary operator τ and a generalized derivation operator δ on the Hilbert-Schmidt class C2(H) which are m-selfadjoint. Finally, we prove that no m-selfadjoint operator on an infinite-dimensional Hilbert space, can be N-supercyclic, for any N≥1.
- Abstract: Publication date: Available online 15 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Maryam Salehi, Karim Hedayatian For a positive integer m and a Hilbert space H an operator T in B(H), the space of all bounded linear operators on H, is called m-selfadjoint if ∑k=0m(−1)k(mk)T⁎kTm−k=0. In this paper, we show that if T∈B(H) and the spectrum of T consists of a finite number of points then it is m-selfadjoint if and only if it is an n-Jordan operator for some integer n. Moreover, we prove that if T is m-selfadjoint then T is nilpotent when it is quasinilpotent. Then we characterize m-selfadjoint weighted shift operators. Also, we show that if T is m-selfadjoint then so is p(T) when p(z) is a polynomial with real coefficients. After that, we investigate an elementary operator τ and a generalized derivation operator δ on the Hilbert-Schmidt class C2(H) which are m-selfadjoint. Finally, we prove that no m-selfadjoint operator on an infinite-dimensional Hilbert space, can be N-supercyclic, for any N≥1.
- A bound for the Waring rank of the determinant via syzygies
- Abstract: Publication date: 15 February 2020Source: Linear Algebra and its Applications, Volume 587Author(s): Mats Boij, Zach Teitler We show that the Waring rank of the 3×3 determinant, previously known to be between 14 and 18, is at least 15. We use syzygies of the apolar ideal, which have not been used in this way before. Additionally, we show that the symmetric cactus rank of the 3×3 permanent is at least 14.
- Abstract: Publication date: 15 February 2020Source: Linear Algebra and its Applications, Volume 587Author(s): Mats Boij, Zach Teitler We show that the Waring rank of the 3×3 determinant, previously known to be between 14 and 18, is at least 15. We use syzygies of the apolar ideal, which have not been used in this way before. Additionally, we show that the symmetric cactus rank of the 3×3 permanent is at least 14.
- On Comon's conjecture over arbitrary fields
- Abstract: Publication date: Available online 14 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Baodong Zheng, Riguang Huang, Xiaoyu Song, Jinli Xu Comon's Conjecture asserts that for a symmetric tensor, the rank is equal to the symmetric rank. For the field of real numbers R or the field of complex numbers C, Zhang et al. proved the conjecture for the case that the rank of a symmetric tensor does not exceed the order. In this paper, we show that over arbitrary fields this conjecture is true when the rank of a tensor is less than its order. Moreover, we construct a counterexample in which the rank of a symmetric tensor whose rank equals its order.
- Abstract: Publication date: Available online 14 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Baodong Zheng, Riguang Huang, Xiaoyu Song, Jinli Xu Comon's Conjecture asserts that for a symmetric tensor, the rank is equal to the symmetric rank. For the field of real numbers R or the field of complex numbers C, Zhang et al. proved the conjecture for the case that the rank of a symmetric tensor does not exceed the order. In this paper, we show that over arbitrary fields this conjecture is true when the rank of a tensor is less than its order. Moreover, we construct a counterexample in which the rank of a symmetric tensor whose rank equals its order.
- On the characterization of digraphs with given rank
- Abstract: Publication date: Available online 12 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Natalia Agudelo, Juan Monsalve, Juan Rada The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2k. In particular, since the bipartite graphs of rank 2,4 and 6 are known, then we characterize digraphs of rank 1,2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication.
- Abstract: Publication date: Available online 12 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Natalia Agudelo, Juan Monsalve, Juan Rada The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2k. In particular, since the bipartite graphs of rank 2,4 and 6 are known, then we characterize digraphs of rank 1,2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication.
- Matrix extremal problems and shift invariant means
- Abstract: Publication date: Available online 11 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Hayoung Choi, Sejong Kim, Hosoo Lee, Yongdo Lim We consider an m×m real symmetric matrix Ma(x) with a1,…,am on the main diagonal and x in all off-diagonal positions, where m≥2 and a=(a1,…,am) is a given m-tuple of positive real numbers. We study the extremal problem of finding the minimum and maximum of x where Ma(x) is positive semidefinite. We show that the polynomial detMa(x) in variable x has only real roots with a unique negative root and that Ma(x) is positive semidefinite (resp. definite) if and only if x lies in the closed (resp. open) interval determined by the negative and smallest positive roots. It is further shown that the negative and smallest positive root maps over m-tuples of positive real numbers contract the Thompson metric and induce new multivariate means of positive real numbers satisfying the monotonicity, homogeneity, joint concavity and super-multiplicativity. In particular, the smallest positive root map extends to such a mean of infinite variable of positive real numbers that realizes the limits for decreasing sequences, and it eventually gives rise to a shift invariant mean of bounded sequences.
- Abstract: Publication date: Available online 11 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Hayoung Choi, Sejong Kim, Hosoo Lee, Yongdo Lim We consider an m×m real symmetric matrix Ma(x) with a1,…,am on the main diagonal and x in all off-diagonal positions, where m≥2 and a=(a1,…,am) is a given m-tuple of positive real numbers. We study the extremal problem of finding the minimum and maximum of x where Ma(x) is positive semidefinite. We show that the polynomial detMa(x) in variable x has only real roots with a unique negative root and that Ma(x) is positive semidefinite (resp. definite) if and only if x lies in the closed (resp. open) interval determined by the negative and smallest positive roots. It is further shown that the negative and smallest positive root maps over m-tuples of positive real numbers contract the Thompson metric and induce new multivariate means of positive real numbers satisfying the monotonicity, homogeneity, joint concavity and super-multiplicativity. In particular, the smallest positive root map extends to such a mean of infinite variable of positive real numbers that realizes the limits for decreasing sequences, and it eventually gives rise to a shift invariant mean of bounded sequences.
- On the rotational invariant L
1-norm PCA
- Abstract: Publication date: Available online 11 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sebastian Neumayer, Max Nimmer, Simon Setzer, Gabriele Steidl Principal component analysis (PCA) is a powerful tool for dimensionality reduction. Unfortunately, it is sensitive to outliers, so that various robust PCA variants were proposed in the literature. One of the most frequently applied methods for high dimensional data reduction is the rotational invariant L1-norm PCA of Ding and coworkers. So far no convergence proof for this algorithm was available. The main topic of this paper is to fill this gap. We reinterpret this robust approach as a conditional gradient algorithm and show moreover that it coincides with a gradient descent algorithm on Grassmann manifolds. Based on the latter point of view, we prove global convergence of the whole series of iterates to a critical point using the Kurdyka-Łojasiewicz property of the objective function, where we have to pay special attention to so-called anchor points, where the function is not differentiable.
- Abstract: Publication date: Available online 11 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sebastian Neumayer, Max Nimmer, Simon Setzer, Gabriele Steidl Principal component analysis (PCA) is a powerful tool for dimensionality reduction. Unfortunately, it is sensitive to outliers, so that various robust PCA variants were proposed in the literature. One of the most frequently applied methods for high dimensional data reduction is the rotational invariant L1-norm PCA of Ding and coworkers. So far no convergence proof for this algorithm was available. The main topic of this paper is to fill this gap. We reinterpret this robust approach as a conditional gradient algorithm and show moreover that it coincides with a gradient descent algorithm on Grassmann manifolds. Based on the latter point of view, we prove global convergence of the whole series of iterates to a critical point using the Kurdyka-Łojasiewicz property of the objective function, where we have to pay special attention to so-called anchor points, where the function is not differentiable.
-
M - Abstract: Publication date: Available online 9 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Luke Evans, Chun-Kit Lai In this paper, we will introduce the notion of conjugate phase retrieval, which is a relaxed definition of phase retrieval allowing recovery of signals up to conjugacy as well as a global phase factor. It is known that frames of real vectors are never phase retrievable on CM in the ordinary sense, but we show that they can be conjugate phase retrievable in complex vector spaces. We continue to develop the theory on conjugate phase retrievable real frames. In particular, a complete characterization of conjugate phase retrievable real frames on C2 and C3 is given. Furthermore, we show that a generic real frame with at least 4M−6 measurements is conjugate phase retrievable in CM for M≥4.
- Abstract: Publication date: Available online 9 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Luke Evans, Chun-Kit Lai In this paper, we will introduce the notion of conjugate phase retrieval, which is a relaxed definition of phase retrieval allowing recovery of signals up to conjugacy as well as a global phase factor. It is known that frames of real vectors are never phase retrievable on CM in the ordinary sense, but we show that they can be conjugate phase retrievable in complex vector spaces. We continue to develop the theory on conjugate phase retrievable real frames. In particular, a complete characterization of conjugate phase retrievable real frames on C2 and C3 is given. Furthermore, we show that a generic real frame with at least 4M−6 measurements is conjugate phase retrievable in CM for M≥4.
- Preservers of restricted unitary orbits of projections
- Abstract: Publication date: Available online 9 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Edward Poon Given a pure state (rank-1 self-adjoint projection) P and a group G of unitary operators acting on a complex Hilbert space, let the restricted unitary orbit of P (relative to G) be UG(P)={UPU−1:U∈G}. We study linear transformations T which map UG(P) into pure states, or more stringently, back into UG(P). A complete characterization is obtained when G is an abelian group of unitary matrices equal to its bicommutant.
- Abstract: Publication date: Available online 9 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Edward Poon Given a pure state (rank-1 self-adjoint projection) P and a group G of unitary operators acting on a complex Hilbert space, let the restricted unitary orbit of P (relative to G) be UG(P)={UPU−1:U∈G}. We study linear transformations T which map UG(P) into pure states, or more stringently, back into UG(P). A complete characterization is obtained when G is an abelian group of unitary matrices equal to its bicommutant.
- Preservers of the left-star and right-star partial orders
- Abstract: Publication date: Available online 7 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Gregor Dolinar, Sait Halicioglu, Abdullah Harmanci, Bojan Kuzma, Janko Marovt, Burcu Ungor Let Mn(F) be the set of all n×n matrices over the field F, where F=R or F=C. We characterize maps on Mn(F) which are surjective and preserve either the left-star or the right-star order in both directions, but are not necessarily additive.
- Abstract: Publication date: Available online 7 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Gregor Dolinar, Sait Halicioglu, Abdullah Harmanci, Bojan Kuzma, Janko Marovt, Burcu Ungor Let Mn(F) be the set of all n×n matrices over the field F, where F=R or F=C. We characterize maps on Mn(F) which are surjective and preserve either the left-star or the right-star order in both directions, but are not necessarily additive.
- Isometric and selfadjoint operators on a vector space with nondegenerate
diagonalizable form- Abstract: Publication date: Available online 7 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Jonathan V. Caalim, Vyacheslav Futorny, Vladimir V. Sergeichuk, Yu-ichi Tanaka Let V be a vector space over a field F with scalar product given by a nondegenerate sesquilinear form whose matrix is diagonal in some basis. If F=C, then we give canonical matrices of isometric and selfadjoint operators on V using known classifications of isometric and selfadjoint operators on a complex vector space with nondegenerate Hermitian form. If F is a field of characteristic different from 2, then we give canonical matrices of isometric, selfadjoint, and skewadjoint operators on V up to classification of symmetric and Hermitian forms over finite extensions of F.
- Abstract: Publication date: Available online 7 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Jonathan V. Caalim, Vyacheslav Futorny, Vladimir V. Sergeichuk, Yu-ichi Tanaka Let V be a vector space over a field F with scalar product given by a nondegenerate sesquilinear form whose matrix is diagonal in some basis. If F=C, then we give canonical matrices of isometric and selfadjoint operators on V using known classifications of isometric and selfadjoint operators on a complex vector space with nondegenerate Hermitian form. If F is a field of characteristic different from 2, then we give canonical matrices of isometric, selfadjoint, and skewadjoint operators on V up to classification of symmetric and Hermitian forms over finite extensions of F.
- Distance-regular graphs with diameter 3 and eigenvalue a
2 − c
3
- Abstract: Publication date: Available online 5 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Quaid Iqbal, Jack H. Koolen, Jongyook Park, Masood Ur Rehman In this paper, we consider the distance-regular graphs Γ whose distance-2 graphs Γ2 are strongly regular. Note that if Γ is bipartite, then its distance-2 graph is not connected. We first show that the distance-2 graph of a non-bipartite distance-regular graph with diameter 3 and eigenvalue a2−c3 is strongly regular, and then we give several kinds of classifications of non-bipartite distance-regular graphs with diameter 3 and eigenvalue a2−c3.
- Abstract: Publication date: Available online 5 November 2019Source: Linear Algebra and its ApplicationsAuthor(s): Quaid Iqbal, Jack H. Koolen, Jongyook Park, Masood Ur Rehman In this paper, we consider the distance-regular graphs Γ whose distance-2 graphs Γ2 are strongly regular. Note that if Γ is bipartite, then its distance-2 graph is not connected. We first show that the distance-2 graph of a non-bipartite distance-regular graph with diameter 3 and eigenvalue a2−c3 is strongly regular, and then we give several kinds of classifications of non-bipartite distance-regular graphs with diameter 3 and eigenvalue a2−c3.
- Lieb functions and sectorial matrices
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Mohammad Alakhrass, Mohammad Sababheh In this article, we present a special treatment of sectorial matrices under Lieb functions. This treatment results from a new characterization of sectorial matrices using blocks, which then implies a new set of inequalities governing such matrices, where singular values, determinants, numerical radius and unitarily invariant norms inequalities are retrieved in a general form that implies many well known results in the literature.
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Mohammad Alakhrass, Mohammad Sababheh In this article, we present a special treatment of sectorial matrices under Lieb functions. This treatment results from a new characterization of sectorial matrices using blocks, which then implies a new set of inequalities governing such matrices, where singular values, determinants, numerical radius and unitarily invariant norms inequalities are retrieved in a general form that implies many well known results in the literature.
- Quadratic tame generators problem of rank three
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Michiel de Bondt, Xiaosong Sun We give a complete classification of quadratic homogeneous polynomial maps H and Keller maps of the form x+H, for which rkJH=3, over a field K of arbitrary characteristic. In particular, we show that such a Keller map is tame when charK≠2.
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Michiel de Bondt, Xiaosong Sun We give a complete classification of quadratic homogeneous polynomial maps H and Keller maps of the form x+H, for which rkJH=3, over a field K of arbitrary characteristic. In particular, we show that such a Keller map is tame when charK≠2.
- Roots of completely positive maps
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): B.V. Rajarama Bhat, Robin Hillier, Nirupama Mallick, Vijaya Kumar U. We introduce the concept of completely positive roots of completely positive maps on operator algebras. We do this in different forms: as asymptotic roots, proper discrete roots and as continuous one-parameter semigroups of roots. We present several general existence and non-existence results, some special examples in settings where we understand the situation better, and several challenging open problems. Our study is closely related to Elfving's embedding problem in classical probability and the divisibility problem of quantum channels.
- Abstract: Publication date: Available online 31 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): B.V. Rajarama Bhat, Robin Hillier, Nirupama Mallick, Vijaya Kumar U. We introduce the concept of completely positive roots of completely positive maps on operator algebras. We do this in different forms: as asymptotic roots, proper discrete roots and as continuous one-parameter semigroups of roots. We present several general existence and non-existence results, some special examples in settings where we understand the situation better, and several challenging open problems. Our study is closely related to Elfving's embedding problem in classical probability and the divisibility problem of quantum channels.
- On the least eigenvalue of A
α
-matrix
of graphs- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Shuting Liu, Kinkar Chandra Das, Shaowei Sun, Jinlong Shu Let G be a graph of order n with m edges and chromatic number χ. Let A(G) be the adjacency matrix and D(G) be the diagonal matrix of vertex degrees of G. Nikiforov defined the matrix Aα(G) as Aα(G)=αD(G)+(1−α)A(G), where 0≤α≤1. Then A12(G)=12(D(G)+A(G))=12Q(G), where Q(G) is the signless Laplacian matrix of G. Let qn(G) and λn(Aα) be the least eigenvalue of Q(G) and Aα(G), respectively. Lima et al. [The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011) 2570–2584] proposed some open problems on qn(G), two of which are as follows:(1) To characterize the graphs for which qn(G)=2mn−1;(2) To characterize the graphs for which qn(G)=(1−1χ−1)2mn.In this paper, we present an upper bound on λn(Aα) in terms of n, m and α (
- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Shuting Liu, Kinkar Chandra Das, Shaowei Sun, Jinlong Shu Let G be a graph of order n with m edges and chromatic number χ. Let A(G) be the adjacency matrix and D(G) be the diagonal matrix of vertex degrees of G. Nikiforov defined the matrix Aα(G) as Aα(G)=αD(G)+(1−α)A(G), where 0≤α≤1. Then A12(G)=12(D(G)+A(G))=12Q(G), where Q(G) is the signless Laplacian matrix of G. Let qn(G) and λn(Aα) be the least eigenvalue of Q(G) and Aα(G), respectively. Lima et al. [The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435 (2011) 2570–2584] proposed some open problems on qn(G), two of which are as follows:(1) To characterize the graphs for which qn(G)=2mn−1;(2) To characterize the graphs for which qn(G)=(1−1χ−1)2mn.In this paper, we present an upper bound on λn(Aα) in terms of n, m and α (
- On the spectral gap of some Cayley graphs on the Weyl group W(B
n
)
- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Filippo Cesi The Laplacian of a (weighted) Cayley graph on the Weyl group W(Bn) is a N×N matrix with N=2nn! equal to the order of the group. We show that for a class of (weighted) generating sets, its spectral gap (lowest nontrivial eigenvalue), is actually equal to the spectral gap of a 2n×2n matrix associated to a 2n-dimensional permutation representation of Wn. This result can be viewed as an extension to W(Bn) of an analogous result valid for the symmetric group, known as “Aldous' spectral gap conjecture”, proven in 2010 by Caputo, Liggett and Richthammer.
- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Filippo Cesi The Laplacian of a (weighted) Cayley graph on the Weyl group W(Bn) is a N×N matrix with N=2nn! equal to the order of the group. We show that for a class of (weighted) generating sets, its spectral gap (lowest nontrivial eigenvalue), is actually equal to the spectral gap of a 2n×2n matrix associated to a 2n-dimensional permutation representation of Wn. This result can be viewed as an extension to W(Bn) of an analogous result valid for the symmetric group, known as “Aldous' spectral gap conjecture”, proven in 2010 by Caputo, Liggett and Richthammer.
- Extreme rays of the ℓ
∞-nearest
ultrametric tropical polytope- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Luyan Yu The set of ultrametrics on [n] nodes that are ℓ∞-nearest to a given dissimilarity map forms a (max,+) tropical polytope. Previous work of Bernstein has given a superset of the set containing all the phylogenetic trees that are extreme rays of this polytope. In this paper, we show that Bernstein's necessary condition of tropical extreme rays is sufficient only for n=3 but not for n≥4. Our proof relies on the exterior description of this tropical polytope, together with the tangent hypergraph techniques for extremality characterization. The sufficiency of the case n=3 is proved by explicitly finding all extreme rays through the exterior description. Meanwhile, an inductive construction of counterexamples is given to show the insufficiency for n≥4.
- Abstract: Publication date: Available online 30 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Luyan Yu The set of ultrametrics on [n] nodes that are ℓ∞-nearest to a given dissimilarity map forms a (max,+) tropical polytope. Previous work of Bernstein has given a superset of the set containing all the phylogenetic trees that are extreme rays of this polytope. In this paper, we show that Bernstein's necessary condition of tropical extreme rays is sufficient only for n=3 but not for n≥4. Our proof relies on the exterior description of this tropical polytope, together with the tangent hypergraph techniques for extremality characterization. The sufficiency of the case n=3 is proved by explicitly finding all extreme rays through the exterior description. Meanwhile, an inductive construction of counterexamples is given to show the insufficiency for n≥4.
- Explicit construction of the eigenvectors and eigenvalues of the graph
Laplacian on the Cayley tree- Abstract: Publication date: Available online 25 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Ayşe Erzan, Aslı Tuncer A generalized Fourier analysis on arbitrary graphs calls for a detailed knowledge of the eigenvectors of the graph Laplacian. Using the symmetries of the Cayley tree, we recursively construct the family of eigenvectors with exponentially growing eigenspaces, associated with eigenvalues in the lower part of the spectrum. The spectral gap decays exponentially with the tree size, for large trees. The eigenvalues and eigenvectors obey recursion relations which arise from the nested geometry of the tree.
- Abstract: Publication date: Available online 25 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Ayşe Erzan, Aslı Tuncer A generalized Fourier analysis on arbitrary graphs calls for a detailed knowledge of the eigenvectors of the graph Laplacian. Using the symmetries of the Cayley tree, we recursively construct the family of eigenvectors with exponentially growing eigenspaces, associated with eigenvalues in the lower part of the spectrum. The spectral gap decays exponentially with the tree size, for large trees. The eigenvalues and eigenvectors obey recursion relations which arise from the nested geometry of the tree.
- Error bounds for computed least squares estimators
- Abstract: Publication date: 1 February 2020Source: Linear Algebra and its Applications, Volume 586Author(s): Xiao-Wen Chang, Peng Kang, David Titley-Peloquin This paper is concerned with normwise errors in the LS estimation for linear regression. It provides probabilistic tail bounds for the normwise error between the computed least squares estimator and the parameter vector, when the least squares problem is solved in floating point arithmetic using either the normal equations method or a backward stable method (for example, using the Householder QR factorization or the singular value decomposition). These bounds are used to provide a condition under which the computationally more efficient normal equations method can safely be used instead of a backward stable method, without any loss of accuracy in the computed estimator.
- Abstract: Publication date: 1 February 2020Source: Linear Algebra and its Applications, Volume 586Author(s): Xiao-Wen Chang, Peng Kang, David Titley-Peloquin This paper is concerned with normwise errors in the LS estimation for linear regression. It provides probabilistic tail bounds for the normwise error between the computed least squares estimator and the parameter vector, when the least squares problem is solved in floating point arithmetic using either the normal equations method or a backward stable method (for example, using the Householder QR factorization or the singular value decomposition). These bounds are used to provide a condition under which the computationally more efficient normal equations method can safely be used instead of a backward stable method, without any loss of accuracy in the computed estimator.
- Normal subgroups of the group of units of incidence algebras
- Abstract: Publication date: 1 February 2020Source: Linear Algebra and its Applications, Volume 586Author(s): Manfred Dugas, Daniel Herden, Jack Rebrovich We investigate the group of units of incidence algebras and its normal subgroups. This includes a detailed discussion of the structure and properties of maximal abelian, normal subgroups, and criteria for solvability and nilpotency.
- Abstract: Publication date: 1 February 2020Source: Linear Algebra and its Applications, Volume 586Author(s): Manfred Dugas, Daniel Herden, Jack Rebrovich We investigate the group of units of incidence algebras and its normal subgroups. This includes a detailed discussion of the structure and properties of maximal abelian, normal subgroups, and criteria for solvability and nilpotency.
- Harmonic equiangular tight frames comprised of regular simplices
- Abstract: Publication date: Available online 23 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Matthew Fickus, Courtney A. Schmitt An equiangular tight frame (ETF) is a sequence of unit-norm vectors in a Euclidean space whose coherence achieves equality in the Welch bound, and thus yields an optimal packing in a projective space. A regular simplex is a simple type of ETF in which the number of vectors is one more than the dimension of the underlying space. More sophisticated examples include harmonic ETFs which equate to difference sets in finite abelian groups. Recently, it was shown that some harmonic ETFs are comprised of regular simplices. In this paper, we continue the investigation into these special harmonic ETFs. We begin by characterizing when the subspaces that are spanned by the ETF's regular simplices form an equi-isoclinic tight fusion frame (EITFF), which is a type of optimal packing in a Grassmannian space. We shall see that every difference set that produces an EITFF in this way also yields a complex circulant conference matrix. Next, we consider a subclass of these difference sets that can be factored in terms of a smaller difference set and a relative difference set. It turns out that these relative difference sets lend themselves to a second, related and yet distinct, construction of complex circulant conference matrices. Finally, we provide explicit infinite families of ETFs to which this theory applies.
- Abstract: Publication date: Available online 23 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Matthew Fickus, Courtney A. Schmitt An equiangular tight frame (ETF) is a sequence of unit-norm vectors in a Euclidean space whose coherence achieves equality in the Welch bound, and thus yields an optimal packing in a projective space. A regular simplex is a simple type of ETF in which the number of vectors is one more than the dimension of the underlying space. More sophisticated examples include harmonic ETFs which equate to difference sets in finite abelian groups. Recently, it was shown that some harmonic ETFs are comprised of regular simplices. In this paper, we continue the investigation into these special harmonic ETFs. We begin by characterizing when the subspaces that are spanned by the ETF's regular simplices form an equi-isoclinic tight fusion frame (EITFF), which is a type of optimal packing in a Grassmannian space. We shall see that every difference set that produces an EITFF in this way also yields a complex circulant conference matrix. Next, we consider a subclass of these difference sets that can be factored in terms of a smaller difference set and a relative difference set. It turns out that these relative difference sets lend themselves to a second, related and yet distinct, construction of complex circulant conference matrices. Finally, we provide explicit infinite families of ETFs to which this theory applies.
- A computational technique in Coxeter spectral study of symmetrizable
integer Cartan matrices- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Daniel Simson With any symmetrizable integer Cartan matrix C∈SCarn⊆Mn(Z), a Z-invertible Coxeter matrix CoxC∈Mn(Z) is associated. We study such positive definite matrices up to a strong Gram Z-congruence C≈ZC′ (defined in the paper by means of a Z-invertible matrix B∈Mn(Z)) by means of the Dynkin type DynC, the complex spectrum speccC⊂C of the Coxeter polynomial coxC(t):=det(tE−CoxC)∈Z[t] and the Coxeter type CtypC=(speccC,swC) of C. We show that the strong Gram Z-congruence C≈ZC′ implies the equality CtypC=CtypC′. The inverse implication is an open problem studied in the paper. However, we prove the implication for positive definite symmetrizable integer Cartan matrices C,C′ satisfying any of the following two conditions: (i) if n≤9, the matrices C,C′ are symmetric (i.e., swC=swC′=1
- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Daniel Simson With any symmetrizable integer Cartan matrix C∈SCarn⊆Mn(Z), a Z-invertible Coxeter matrix CoxC∈Mn(Z) is associated. We study such positive definite matrices up to a strong Gram Z-congruence C≈ZC′ (defined in the paper by means of a Z-invertible matrix B∈Mn(Z)) by means of the Dynkin type DynC, the complex spectrum speccC⊂C of the Coxeter polynomial coxC(t):=det(tE−CoxC)∈Z[t] and the Coxeter type CtypC=(speccC,swC) of C. We show that the strong Gram Z-congruence C≈ZC′ implies the equality CtypC=CtypC′. The inverse implication is an open problem studied in the paper. However, we prove the implication for positive definite symmetrizable integer Cartan matrices C,C′ satisfying any of the following two conditions: (i) if n≤9, the matrices C,C′ are symmetric (i.e., swC=swC′=1
- Trees with a large Laplacian eigenvalue multiplicity
- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): S. Akbari, E.R. van Dam, M.H. Fakharan In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. It is known that for trees, integer Laplacian eigenvalues larger than 1 are simple and also the multiplicity of Laplacian eigenvalue 1 has been well studied before. Here we consider the multiplicities of the other (non-integral) Laplacian eigenvalues. We give an upper bound and determine the trees of order n that have a multiplicity that is close to the upper bound n−32, and emphasize the particular role of the algebraic connectivity.
- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): S. Akbari, E.R. van Dam, M.H. Fakharan In this paper, we study the multiplicity of the Laplacian eigenvalues of trees. It is known that for trees, integer Laplacian eigenvalues larger than 1 are simple and also the multiplicity of Laplacian eigenvalue 1 has been well studied before. Here we consider the multiplicities of the other (non-integral) Laplacian eigenvalues. We give an upper bound and determine the trees of order n that have a multiplicity that is close to the upper bound n−32, and emphasize the particular role of the algebraic connectivity.
- Affine and Projective Planes Linked with Projective Lines over Certain
Rings of Lower Triangular Matrices- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Edyta Bartnicka, Metod Saniga Let Tn(q) be the ring of lower triangular matrices of order n≥2 with entries from the finite field F(q) of order q≥2 and let Tn2(q) denote its free left module. For n=2,3 it is shown that the projective line over Tn(q) gives rise to a set of (q+1)(n−1)q3(n−1)(n−2)2 affine planes of order q. The points of such an affine plane are non-free cyclic submodules of Tn2(q) not contained in any non-unimodular free cyclic submodule of Tn2(q) and its lines are points of the projective line. Furthermore, it is demonstrated that each affine plane can be extended to the projective plane of order q, with the ‘line at infinity’ being represented by those free cyclic submodules of Tn2(q) that are generated by non-unimodular pairs. Our approach can be adjusted to address the case of arbitrary n.
- Abstract: Publication date: Available online 22 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Edyta Bartnicka, Metod Saniga Let Tn(q) be the ring of lower triangular matrices of order n≥2 with entries from the finite field F(q) of order q≥2 and let Tn2(q) denote its free left module. For n=2,3 it is shown that the projective line over Tn(q) gives rise to a set of (q+1)(n−1)q3(n−1)(n−2)2 affine planes of order q. The points of such an affine plane are non-free cyclic submodules of Tn2(q) not contained in any non-unimodular free cyclic submodule of Tn2(q) and its lines are points of the projective line. Furthermore, it is demonstrated that each affine plane can be extended to the projective plane of order q, with the ‘line at infinity’ being represented by those free cyclic submodules of Tn2(q) that are generated by non-unimodular pairs. Our approach can be adjusted to address the case of arbitrary n.
- PI-eigenfunctions of the Star graphs
- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sergey Goryainov, Vladislav Kabanov, Elena Konstantinova, Leonid Shalaginov, Alexandr Valyuzhenich We consider the symmetric group Symn, n⩾2, generated by the set S of transpositions (1i),2⩽i⩽n, and the Cayley graph Sn=Cay(Symn,S) called the Star graph. For any positive integers n⩾3 and m with n>2m, we present a family of eigenfunctions of Sn with eigenvalue n−m−1 and call them PI-eigenfunctions. We then establish a connection of these functions with the standard basis of a Specht module. Finally, in the case of the largest non-principal eigenvalue n−2 we prove that any eigenfunction of Sn can be reconstructed by its values on the second neighbourhood of a vertex.
- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sergey Goryainov, Vladislav Kabanov, Elena Konstantinova, Leonid Shalaginov, Alexandr Valyuzhenich We consider the symmetric group Symn, n⩾2, generated by the set S of transpositions (1i),2⩽i⩽n, and the Cayley graph Sn=Cay(Symn,S) called the Star graph. For any positive integers n⩾3 and m with n>2m, we present a family of eigenfunctions of Sn with eigenvalue n−m−1 and call them PI-eigenfunctions. We then establish a connection of these functions with the standard basis of a Specht module. Finally, in the case of the largest non-principal eigenvalue n−2 we prove that any eigenfunction of Sn can be reconstructed by its values on the second neighbourhood of a vertex.
- Characterization of k−smooth operators between Banach
spaces- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Arpita Mal, Kallol Paul We study k−smoothness of bounded linear operators defined between arbitrary Banach spaces. As an application, we characterize k−smooth operators defined from ℓ1n to an arbitrary Banach space. We also completely characterize k−smooth operators defined between arbitrary two-dimensional Banach spaces.
- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Arpita Mal, Kallol Paul We study k−smoothness of bounded linear operators defined between arbitrary Banach spaces. As an application, we characterize k−smooth operators defined from ℓ1n to an arbitrary Banach space. We also completely characterize k−smooth operators defined between arbitrary two-dimensional Banach spaces.
- Non-singular derivations of solvable Lie algebras in prime characteristic
- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Marcos Goulart Lima, Csaba Schneider We study solvable Lie algebras in prime characteristic p that admit non-singular derivations. We show that Jacobson's Theorem remains true if the quotients of the derived series have dimension less than p. We also study the structure of Lie algebras with non-singular derivations in which the derived subalgebra is abelian and has codimension one. The paper presents some new examples of solvable, but not nilpotent, Lie algebras of derived length 3 with non-singular derivations.
- Abstract: Publication date: Available online 21 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Marcos Goulart Lima, Csaba Schneider We study solvable Lie algebras in prime characteristic p that admit non-singular derivations. We show that Jacobson's Theorem remains true if the quotients of the derived series have dimension less than p. We also study the structure of Lie algebras with non-singular derivations in which the derived subalgebra is abelian and has codimension one. The paper presents some new examples of solvable, but not nilpotent, Lie algebras of derived length 3 with non-singular derivations.
- Inequalities for generalized derivations of operator monotone functions in
norm ideals of compact operators- Abstract: Publication date: Available online 18 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Danko R. Jocić, Milan Lazarević, Stefan Milošević Let Φ be a symmetrically norming (s.n.) function, p⩾2, Φ(p)⁎ to be a dual s.n. function to p-modified s.n. function Φ(p),
with A and B being normal operators such that 
If both A and B are strictly accretive, then for non-constant Pick function φ∈P[0,+∞)(1) φ(A)X−Xφ(B) Φ⩽ φ′(A⁎+A2)(AX−XB)φ′(B+B⁎2) Φ. If A and B have strictly contractive real parts, then12 I− A⁎+A2 2(logI+AI−AX−XlogI+BI−B)...
- Abstract: Publication date: Available online 18 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Danko R. Jocić, Milan Lazarević, Stefan Milošević Let Φ be a symmetrically norming (s.n.) function, p⩾2, Φ(p)⁎ to be a dual s.n. function to p-modified s.n. function Φ(p),
-
R , S - Abstract: Publication date: Available online 15 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Rosário Fernandes, Henrique F. da Cruz, Susana C. Palheira Let R and S be two sequences of nonnegative integers in nonincreasing order which have the same sum, and let A(R,S) be the class of all (0,1)-matrices which have row sums given by R and column sums given by S. For a positive integer t, the t-term rank of a (0,1)-matrix A is defined as the maximum number of 1's in A with at most one 1 in each column and at most t 1's in each row. In this paper, we address conditions for the existence of a matrix in A(R,S) that realizes all the minimum t-term ranks, for t≥1.
- Abstract: Publication date: Available online 15 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Rosário Fernandes, Henrique F. da Cruz, Susana C. Palheira Let R and S be two sequences of nonnegative integers in nonincreasing order which have the same sum, and let A(R,S) be the class of all (0,1)-matrices which have row sums given by R and column sums given by S. For a positive integer t, the t-term rank of a (0,1)-matrix A is defined as the maximum number of 1's in A with at most one 1 in each column and at most t 1's in each row. In this paper, we address conditions for the existence of a matrix in A(R,S) that realizes all the minimum t-term ranks, for t≥1.
- Multidimensional permanents of polystochastic matrices
- Abstract: Publication date: Available online 15 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Billy Child, Ian M. Wanless A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal.For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1)) 1-permutation matrices and contains a polytope of dimension at least cn3/2 for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent.For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.
- Abstract: Publication date: Available online 15 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Billy Child, Ian M. Wanless A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal.For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least nn3/2(1/2−o(1)) 1-permutation matrices and contains a polytope of dimension at least cn3/2 for fixed c,d and even n→∞. We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent.For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.
- An extremal problem for integer sparse recovery
- Abstract: Publication date: Available online 11 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sergei Konyagin, Benny Sudakov Motivated by the problem of integer sparse recovery we study the following question. Let A be an m×d integer matrix whose entries are in absolute value at most k. How large can be d=d(m,k) if all m×m submatrices of A are non-degenerate' We obtain new upper and lower bounds on d and answer a special case of the problem by Brass, Moser and Pach on covering m-dimensional k×⋯×k grid by linear subspaces.
- Abstract: Publication date: Available online 11 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): Sergei Konyagin, Benny Sudakov Motivated by the problem of integer sparse recovery we study the following question. Let A be an m×d integer matrix whose entries are in absolute value at most k. How large can be d=d(m,k) if all m×m submatrices of A are non-degenerate' We obtain new upper and lower bounds on d and answer a special case of the problem by Brass, Moser and Pach on covering m-dimensional k×⋯×k grid by linear subspaces.
- Mixed paths and cycles determined by their spectrum
- Abstract: Publication date: Available online 1 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): S. Akbari, A. Ghafari, M. Nahvi, M.A. Nematollahi A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set {v1,…,vn}, is the matrix H=[hij]n×n, where hij=−hji=i if there is a directed edge from vi to vj, hij=1 if there exists an undirected edge between vi and vj, and hij=0 otherwise. The Hermitian spectrum of a mixed graph is defined to be the spectrum of its Hermitian adjacency matrix.In this paper we study mixed graphs which are determined by their Hermitian spectrum (DHS). First, we show that each mixed cycle is switching equivalent to either a mixed cycle with no directed edges (Cn), a mixed cycle with exactly one directed edge (Cn1), or a mixed cycle with exactly two consecutive directed edges with the same direction (Cn2) and we determine the spectrum of these three types of cycles. Next, we characterize all DHS mixed paths and mixed cycles. We show that all mixed paths of even order, except P8 and P14, are DHS. It is also shown that mixed paths of odd order, except P3, are not DHS. Also, all cospectral mates of P8, P14 and P4k+1 and two families of cospectral mates of P4k+3, where k≥1, are introduced. Finally, we show that the mixed cycles C2k and C2k2, where k≥3, are not DHS...
- Abstract: Publication date: Available online 1 October 2019Source: Linear Algebra and its ApplicationsAuthor(s): S. Akbari, A. Ghafari, M. Nahvi, M.A. Nematollahi A mixed graph is obtained from a graph by orienting some of its edges. The Hermitian adjacency matrix of a mixed graph with the vertex set {v1,…,vn}, is the matrix H=[hij]n×n, where hij=−hji=i if there is a directed edge from vi to vj, hij=1 if there exists an undirected edge between vi and vj, and hij=0 otherwise. The Hermitian spectrum of a mixed graph is defined to be the spectrum of its Hermitian adjacency matrix.In this paper we study mixed graphs which are determined by their Hermitian spectrum (DHS). First, we show that each mixed cycle is switching equivalent to either a mixed cycle with no directed edges (Cn), a mixed cycle with exactly one directed edge (Cn1), or a mixed cycle with exactly two consecutive directed edges with the same direction (Cn2) and we determine the spectrum of these three types of cycles. Next, we characterize all DHS mixed paths and mixed cycles. We show that all mixed paths of even order, except P8 and P14, are DHS. It is also shown that mixed paths of odd order, except P3, are not DHS. Also, all cospectral mates of P8, P14 and P4k+1 and two families of cospectral mates of P4k+3, where k≥1, are introduced. Finally, we show that the mixed cycles C2k and C2k2, where k≥3, are not DHS...
