• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 25
Sort:
by name
by year
Article
Shitov Y. Linear Algebra and its Applications. 2017. Vol. 513. P. 120-121.

We construct a counterexample to the following conjecture, which was proposed recently by Bapat et al. ‘If a is a regular element in a semigroup S, and x is an outer inverse of a, then a has a reflexive generalized inverse y which dominates x with respect to the minus order on S.’

Added: Oct 21, 2016
Article
Shitov Y. Linear Algebra and its Applications. 2016. Vol. 511. P. 19-21.

Let K be a field with non-Archimedean valuation v, and assume A is a matrix of size m×n and rank k over K. Richter- Gebert, Sturmfels, and Theobald proved that the rows of A are a tropical basis of the corresponding linear space whenever m = k and any submatrix formed by k columns of v(A) has tropical rank k. We show that this result is no longer true without assumption m = k, refuting the conjecture proposed by Yu and Yuster in 2007. 

Added: Sep 7, 2016
Article
Shitov Y. Linear Algebra and its Applications. 2016. Vol. 497. P. 62-65.

The max-times algebra is the set R+ of nonnegative reals with operations ⊕:(a,b)→max⁡{a,b} and ⊙:(a,b)→ab. We discuss the property of matrices to be squares of max-times or conventional nonnegative matrices. We prove that there exists a matrix having a conventional nonnegative square root but no max-times square root. Also, we present a set S of cardinality three for which there is a nonnegative matrix with spectrum S, and every such M has both conventional and max-times square roots. These results answer two questions from the recent paper by Tam and Huang.

Added: Feb 23, 2016
Article
Stukopin V. Linear Algebra and its Applications. 2019. Vol. 580. No. 1. P. 292-335.

This paper is devoted to the asymptotic behavior of all eigenvalues of the increasing finite principal sections of an infinite symmetric (in general non-Hermitian) Toeplitz matrix. The symbol of the infinite matrix is supposed to be moderately smooth and to trace out a simple loop in the complex plane. The main result describes the asymptotic structure of all eigenvalues. The asymptotic expansions constructed are uniform with respect to the location of the eigenvalues in the bulk of the spectrum.

Added: Mar 1, 2020
Article
Shitov Y. Linear Algebra and its Applications. 2015. Vol. 466. P. 38-40.

A generating set G of a left semimodule S over a semiring R is called a basis if no proper subset of G generates S. We prove that Rn has no basis of cardinality exceeding qn, where q is the largest cardinality of bases of R.

Added: Oct 30, 2014
Article
Shitov Y. Linear Algebra and its Applications. 2018. Vol. 553. P. 362-364.

Let F be a field. Any continuous function f from Fn×n to Fn×n satisfying xf(x) ≡ f(x)x can be written as

f(x) ≡ α_0(x)x_0 + . . . + α_{n−1}(x)x_{n−1}

with α : F^{n×n} → F^n continuous on the set of non-derogatory matrices. Brešar and Šemrl showed this for F = C, and we give a proof valid over any topological field. For F ∈ {R,C}, we provide an example of a function f for which any appropriate α is discontinuous at every derogatory matrix.

Added: Sep 26, 2018
Article
Shitov Y. Linear Algebra and its Applications. 2016. Vol. 508. P. 225-233.

Let R be a commutative semiring and S be an R-semimodule with inner product operation. A subset B ⊂ S is called standard orthogonal if, for any different b, c ∈ B, ⟨b, b⟩ is a unit and ⟨b, c⟩ = 0. Tan posed the following problem: Characterize semirings R such that, for every R-semimodule with standard orthogonal basis and every standard orthogonal set B ⊂ S, there is a standard orthogonal basis of S containing B. In this paper, we present a negative result on this problem. Namely, we show that such a description is not possible in terms of first-order logic. Also, we provide several interesting examples related to the problem. 

Added: Jul 27, 2016
Article
Shitov Y. Linear Algebra and its Applications. 2011. Vol. 435. No. 7. P. 1769-1777.

The rank-sum, rank-product, and rank-union inequalities for Gondran–Minoux rank of matrices over idempotent semirings are considered. We prove these inequalities for matrices over quasi-selective semirings without zero divisors, which include matrices over the max-plus semiring. Moreover, it is shown that the inequalities provide the linear algebraic characterization for the class of quasi-selective semirings. Namely, it is proven that the inequalities hold for matrices over an idempotent semiring S without zero divisors if and only if S is quasi-selective. For any idempotent semiring which is not quasi-selective it is shown that the rank-sum, rank-product, and rank-union inequalities do not hold in general. Also, we provide an example of a selective semiring with zero divisors such that the rank-sum, rank-product, and rank-union inequalities do not hold in general.

Added: Jan 25, 2013
Article
Protasov V. Y., Jungers R. Linear Algebra and its Applications. 2013. Vol. 438. No. 11. P. 4448-4468.

We introduce a new approach to evaluate the largest Lyapunov exponent of a family of nonnegative matrices. The method is based on using special positive homogeneous functionals on , which gives iterative lower and upper bounds for the Lyapunov exponent. They improve previously known bounds and converge to the real value. The rate of convergence is estimated and the efficiency of the algorithm is demonstrated on several problems from applications (in functional analysis, combinatorics, and language theory) and on numerical examples with randomly generated matrices. The method computes the Lyapunov exponent with a prescribed accuracy in relatively high dimensions (up to 60). We generalize this approach to all matrices, not necessarily nonnegative, derive a new universal upper bound for the Lyapunov exponent, and show that a potential similar lower bound does not exist in general.

Added: Feb 23, 2016
Article
Protasov V. Y., Voinov A. S. Linear Algebra and its Applications. 2017. No. 513. P. 376-408.

Multiplicative matrix semigroups with constant spectral radius (c.s.r.) are studied and applied to several problems of algebra, combinatorics, functional equations, and dynamical systems. We show that all such semigroups are characterized by means of irreducible ones. Each irreducible c.s.r. semigroup defines walks on Euclidean sphere, all its nonsingular elements are similar (in the same basis) to orthogonal. We classify all nonnegative c.s.r. semigroups and arbitrary low-dimensional semigroups. For higher dimensions, we describe five classes and leave an open problem on completeness of that list. The problem of algorithmic recognition of c.s.r. property is proved to be polynomially solvable for irreducible semigroups and undecidable for reducible ones.

Added: Mar 11, 2017
Article
Yurii Burman, Ploskonosov A., Trofimova A. Linear Algebra and its Applications. 2015. No. 466C. P. 64-82.

We calculate characteristic polynomials of operators explicitly presented as polynomials of rank 1 operators. Corollaries of the main result (Theorem 1) include a generalization of the Forman's formula for the determinant of the graph Laplacian, the celebrated Matrix-tree theorem by G.Kirchhoff, and some its generalizations and analogs, both known (e.g. the Matrix-hypertree theorem by G.Masbaum and A.Vaintrob) and new.  

Added: Apr 4, 2014
Article
Alisa Chistopolskaya. Linear Algebra and its Applications. 2018. No. 559. P. 73-79.

Consider the special linear Lie algebra sl_n(K) over an infinite field of characteristic different from 2. We prove that for any nonzero nilpotent X there exists a nilpotent Y such that the matrices X and Y generate the Lie algebra sl_n(K).

Added: Sep 19, 2019
Article
Shitov Y. Linear Algebra and its Applications. 2016. Vol. 499. P. 26-30.

Let χ(A) denote the characteristic polynomial of a matrix A over a field; a standard result of linear algebra states that χ(A−1) is the reciprocal polynomial of χ(A). More formally, the condition χn(A)χk(A−1) = χn−k(A) holds for any invertible n × n matrix A over a field, where χi(A) denotes the coefficient of λn−i in the characteristic polynomial det(λI − A). We confirm a recent conjecture of Niv by proving the tropical analogue of this result. 

 

Added: Mar 9, 2016
Article
Yaroslav Shitov. Linear Algebra and its Applications. 2013. Vol. 439. No. 8. P. 2500-2502.

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute.

Added: Aug 11, 2013
Article
Shitov Y. Linear Algebra and its Applications. 2018. Vol. 554. P. 49-50.

We prove that the determinant of an n-by-n 0-1 matrix with at most n + k non-zero entries does not exceed α^k with α ≈ 1.316074.

Added: Sep 26, 2018
Article
Shitov Y. Linear Algebra and its Applications. 2018. Vol. 554. P. 49-50.

We prove that the determinant of an n x n 01-matrix with at most n+k non-zero entries does not exceed α^k with α=4^(1/3)≈1.316074.

Added: Jan 30, 2019
Article
Shitov Y. Linear Algebra and its Applications. 2012. Vol. 436. No. 9. P. 3247-3253.

We investigate the Kapranov rank functions of tropical matrices for different ground fields. For any infinite ground field we show that the rank-product inequality holds for Kapranov rank, and we prove that the Kapranov rank respects Green’s preorders on the semigroup of tropical n-by-n matrices. The rank-product inequality is shown to fail for Kapranov rank over any finite ground field. We provide an example of a 7-by-7 01-matrixwhose Kapranov rank is independent of a ground field, equals 6, and exceeds tropical rank.

Added: Nov 9, 2012
Article
Shitov Y. Linear Algebra and its Applications. 2018. Vol. 544. P. 299-305.

An n×n matrix A is called permutative if the rows of A are distinct permutations of a family of n distinct elements. For all n⩾3, we show that the minimal rank of a non-negative permutative matrix equals 3. The minimal rank of a generic permutative n×n matrix equals the smallest integer r such that r!⩾n. Our results answer the questions asked recently by Hu, Johnson, Davis, Zhang, and we show how to generalize them to tensors.

Added: Jan 30, 2019
Article
Shitov Y. Linear Algebra and its Applications. 2012. Vol. 437. No. 11. P. 2727-2732.

The notion of the factor rank of tropical matrices is considered. We construct a linear-time algorithm that either finds a full-rank 3 × 3 submatrix of a given matrix or concludes that the factor rank of is less than 3. We show that there exist matrices of factor rank 4 whose 4 × 4 submatrices are all rank deficient.

Added: Jan 6, 2013
Article
Alexander Guterman, Yaroslav Shitov. Linear Algebra and its Applications. 2016. Vol. 498. P. 326-348.

We consider rank functions important in tropical linear algebra: the tropical rank, equal to the topological dimension of the tropical linear span of the columns of a given matrix, the factor rank, equal to the smallest number of vectors containing these columns in their span, the Kapranov rank, related to problems of tropical algebraic geometry, and the determinantal and Gondran–Minoux ranks, which generalize the classical linear algebraic notion of rank. We are interested in studying the arithmetic properties of the rank functions, their mutual behavior, and the related computational problems. We discuss different open problems related to rank functions of tropical matrices and illustrate them by the number of examples.

Added: Aug 10, 2015
Article
Voinov A. S. Linear Algebra and its Applications. 2013. Vol. 439. No. 15. P. 1627-1634.

Let A = {A_1, ..., A_m} be a set of nonnegative dxd matrices having at least one strictly positive product (all products with no ordering and with repetitions permitted). What is the minimal possible length of their positive product? In other words, what is the minimal number l(A) for which there are indices i_1, ..., i_l(A) \in {1, ..., m} such that the matrix A_{i_1}...A_{i_l(A)} has all entries positive? In this paper we show, under some mild assumptions on matrices, that l(A) \leq (d^3 + d^2) / 2 - 2d + 1. We apply this result to estimate the rate of convergence in some limit theorems for random matrices.

Added: Mar 14, 2017
1 2