Growth in products of matrices: fastest, average, and generic

• URL: http://arxiv.org/abs/2405.00610v5
• Date: Tue, 18 Jun 2024 06:49:09 GMT
• Title: Growth in products of matrices: fastest, average, and generic
• Abstract summary: We answer three questions about a random matrix product. For the third question, we offer a very simple method to produce an upper bound on the Lyapunov exponent.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problems that we consider in this paper are as follows. Let A and B be 2x2 matrices (over reals). Let w(A, B) be a word of length n. After evaluating w(A, B) as a product of matrices, we get a 2x2 matrix, call it W. What is the largest (by the absolute value) possible entry of W, over all w(A, B) of length n, as a function of n? What is the expected absolute value of the largest (by the absolute value) entry in a random product of n matrices, where each matrix is A or B with probability 0.5? What is the Lyapunov exponent for a random matrix product like that? We give partial answer to the first of these questions and an essentially complete answer to the second question. For the third question (the most difficult of the three), we offer a very simple method to produce an upper bound on the Lyapunov exponent in the case where all entries of the matrices A and B are nonnegative.

Related papers

• GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding [54.10836630612739]
  GPTQ, or equivalently Babai's nearest plane algorithm, rounds a real matrix to integers under a quadratic metric.<n>We present GPTQ-2D, which produces the identical rounded matrix in cubic time.
  arXiv  Detail & Related papers  (2026-07-29T15:34:00Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• The Structural Complexity of Matrix-Vector Multiplication [0.10485739694839669]
  We show that the matrix-vector multiplication problem can be solved with $tildeO(n2)$ preprocessing and $tilde O(n2-1/d)$ query time. Our results yield the first non-trivial upper bounds for many applications.
  arXiv  Detail & Related papers  (2025-02-28T17:11:36Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• A random copositive matrix is completely positive with positive probability [0.0]
  An $ntimes n$ symmetric matrix $A$ is copositive if the quadratic form $xTAx$ is nonnegative on the nonnegative orthant. The main result, proved using Blekherman's real algebraic geometry inspired techniques and tools of convex geometry, shows that as $n$ goes to infinity, the ratio of volume radii of the two cones is strictly positive.
  arXiv  Detail & Related papers  (2023-05-25T16:30:58Z)
• Real Schur norms and Hadamard matrices [0.0]
  We present a preliminary study of Schur norms $|M|_S=max |Mcirc C|: |C|=1$, where M is a matrix whose entries are $pm1$, and $circ$ denotes the entrywise (i.e., Schur or Hadamard) product of the matrix. We show that, if such a matrix M is n-by-n, then its Schur norm is bounded by $sqrtn$, and equality holds if and only
  arXiv  Detail & Related papers  (2022-06-06T19:30:13Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• On a matrix equality involving partial transposition and its relation to the separability problem [1.0867097571641349]
  In matrix theory, a well established relation $(AB)T=BTAT$ holds for any two matrices $A$ and $B$ for which the product $AB$ is defined. We explore the possibility of deriving the matrix equality $(AB)Gamma=AGammaBGamma$ for any $4 times 4$ matrices $A$ and $B$, where $Gamma$ denote the partial transposition.
  arXiv  Detail & Related papers  (2021-04-13T11:46:43Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
  Singular Value Decomposition (SVD) is a well studied research topic in many fields and applications. We propose Ranky, set of methods to solve rank problem on large and sparse matrices in a distributed manner.
  arXiv  Detail & Related papers  (2020-09-21T11:36:28Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field. We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
  arXiv  Detail & Related papers  (2020-06-24T19:33:49Z)
• The decomposition of an arbitrary $2^w\times 2^w$ unitary matrix into signed permutation matrices [0.0]
  Birkhoff's theorem tells that any doubly matrix can be decomposed as a weighted sum of permutation matrices. A similar theorem reveals that any unitary matrix can be decomposed as a weighted sum of complex permutation matrices.
  arXiv  Detail & Related papers  (2020-05-26T18:26:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.