Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix

• URL: http://arxiv.org/abs/2109.01740v1
• Date: Fri, 3 Sep 2021 21:56:14 GMT
• Title: Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
• Authors: Vitaly V. Kocharovsky, Vladimir V. Kocharovsky, Vladimir Yu. Martyanov, Sergey V. Tarasov
• Abstract summary: The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulants. Its solution would be tremendously important for a unified analysis of a wide range of the nature's #P-hard problems.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a finite-order system of recurrence relations for a permanent of circulant matrices containing a band of k any-value diagonals on top of a uniform matrix (for k = 1, 2, and 3) as well as the method for deriving such recurrence relations which is based on the permanents of the matrices with defects. The proposed system of linear recurrence equations with variable coefficients provides a powerful tool for the analysis of the circulant permanents, their fast, linear time computing and finding their asymptotics in a large-matrix-size limit. The latter problem is an open fundamental problem. Its solution would be tremendously important for a unified analysis of a wide range of the nature's #P-hard problems, including problems in the physics of many-body systems, critical phenomena, quantum computing, quantum field theory, theory of chaos, fractals, theory of graphs, number theory, combinatorics, cryptography, etc.

Related papers

• On subdifferential chain rule of matrix factorization and beyond [20.82938951566065]
  We show equality-type Clarke subdifferential chain rules of matrix factorization and factorization machine. Some tensor generalizations and neural extensions are also discussed, albeit they remain mostly open.
  arXiv  Detail & Related papers  (2024-10-07T13:24:59Z)
• Eigenstate Correlations in Dual-Unitary Quantum Circuits: Partial Spectral Form Factor [0.0]
  Analytic insights into eigenstate correlations can be obtained by the recently introduced partial spectral form factor. We study the partial spectral form factor in chaotic dual-unitary quantum circuits in the thermodynamic limit.
  arXiv  Detail & Related papers  (2024-07-29T12:02:24Z)
• Positive Moments Forever: Undecidable and Decidable Cases [1.3124513975412255]
  We show that the positivity problem for simple unitary linear recurrence sequences is decidable, and is undecidable for linear recurrence sequences over the ring of commutatives. As a byproduct, we prove a free version of Polya's theorem.
  arXiv  Detail & Related papers  (2024-04-23T13:53:37Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  Sparse matrix factorization is the problem of approximating a matrix Z by a product of L sparse factors X(L) X(L--1). This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed.
  arXiv  Detail & Related papers  (2021-10-04T07:56:37Z)
• The Transfer Matrix Method and The Theory of Finite Periodic Systems. From Heterostructures to Superlattices [0.0]
  Long-period systems and superlattices have new effects on the energy spectrum and wave functions. Most approaches adjust theories for infinite systems, which is acceptable for small number of unit cells $n$. We review some applications of the transfer-matrix method with Floquet's theorem to negative resistance, ballistic transistors, channel coupling, spintronics, superluminal, and optical antimatter effects.
  arXiv  Detail & Related papers  (2021-09-23T20:45:29Z)
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time [46.31710224483631]
  We show how to bypass the main open question of Nelson and Nguyen (FOCS, 2013) regarding the logarithmic factors in the sketching dimension for existing constant factor approximation oblivious subspace embeddings. A key technique we use is an explicit mapping of Indyk based on uncertainty principles and extractors. For the fundamental problems of rank computation and finding a linearly independent subset of columns, our algorithms improve Cheung, Kwok, and Lau (JACM, 2013) and are optimal to within a constant factor and a $loglog(n)$-factor, respectively.
  arXiv  Detail & Related papers  (2021-07-16T19:34:10Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)

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.