Higher matrix-tree theorems
arxiv.org. math. Cornell University , 2011. No. 1109.6625.
Burman Y. M., Ploskonosov A., Trofimova A.
We calculate determinants of weighted sums of reflections and of (nested) commutators of reflections. The results obtained generalize the matrix-tree theorem by Kirchhoff and the Pfaffian-hypertree theorem by Massbaum and Vaintrob.
Research target: Mathematics
Priority areas: IT and mathematics
, Journal of Algebraic Combinatorics 2019 Vol. 50 No. 4 P. 427-446
The classical matrix-tree theorem discovered by G.Kirchhoff in 1847 expresses the principal minor of the (n x n) Laplace matrix as a sum of monomials of matrix elements indexed by directed trees with n vertices. We prove, for any k >= n, a three-parameter family of identities between degree k polynomials of matrix elements of the Laplace matrix. For k=n and special values of ...
Added: October 18, 2018
, , Linear Algebra and its Applications 2012 Vol. 437 No. 7 P. 1793-1811
We introduce the notion of the tropical matrix pattern, which provides a powerful tool to investigate tropical matrices. The above approach is then illustrated by the application to the study of the properties of the Gondran–Minoux rank function. Our main result states that up to a multiplication of matrix rows by non-zero constants the Gondran–Minoux independence ...
Added: November 9, 2012
, 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 ...
Added: November 9, 2012
, Известия высших учебных заведений. Математика 2011 № 3 С. 86-94
Приводится квазиполиномиальный алгоритм распознавания подобия над кольцом целых чисел матриц, имеющих целочисленный спектр и жорданова форма которых не содержит клеток одинакового порядка для одного и того же собственного числа. Если алгебраическая кратность всех собственных чисел равна 1, то оценивается число классов подобия. ...
Added: October 25, 2012
, , et al., Linear Algebra and its Applications 2023 Vol. 666 P. 129-143
In this paper, we characterize the automorphisms of the total graph for the ring M_n of matrices of order n≥2 over any field with at least 3 elements. To do this, we apply the technique of maps preserving matrix invariants; in particular, as an intermediate step, we characterize pairs of surjective maps φ_1,φ_2:M_n →M_n such that A+B is singular if and only if φ_1(A)+φ_2(B) is ...
Added: April 11, 2023
, , Известия высших учебных заведений. Математика 2006 № 4 С. 57-64
Хорошо изученное понятие подобия матриц над полем рациональных чисел естественным образом переносится на кольцо целых чисел. Сильно возросшие трудности заставили ограничиться двумерным случаем, в котором получен алгоритм проверки подобия двух матриц над Z и, если их характеристический многочлен приводим над Q, описаны классы подобных матриц. ...
Added: October 25, 2012
, , , 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: April 4, 2014
On computing the determinant, other characteristic polynomial coefficients, and inverse in Clifford algebras of arbitrary dimension
, Computational and Applied Mathematics 2021 Vol. 40 P. 1-29
In this paper, we solve the problem of computing the inverse in Clifford algebras of arbitrary dimension. We present basis-free formulas of different types (explicit and recursive) for the determinant, other characteristic polynomial coefficients, adjugate, and inverse in real Clifford algebras (or geometric algebras) over vector spaces of arbitrary dimension $n$. The formulas involve only ...
Added: July 15, 2021
, Higher determinants and the matrix-tree theorem / Cornell University. Series math "arxiv.org". 2015. No. 1508.02245.
We prove a generalization of the (nonsymmetric) matrix-tree theorem containing no trees and essentially no matrices. Instead of trees we consider acyclic directed graphs with a prescribed set of sinks, and instead of determinant, a polynomial invariant of the matrix determined by directed graph such that any two vertices of the same connected component are ...
Added: October 9, 2015
, Journal of Algebra 2012 Vol. 370 P. 1-4
The paper gives a complete description of the subgroups of the semigroup of tropical n-by-n matrices up to an isomorphism. ...
Added: November 7, 2012
, , Russian Journal of Mathematical Physics 2021 Vol. 28 No. 2 P. 179-187
In this paper, we show how to construct an asymptotic representation of the fundamental solution to the Cauchy problem for degenerate linear parabolic equations. ...
Added: June 6, 2021
Agent-based modelling of interactions between air pollutants and greenery using a case study of Yerevan, Armenia
, , , Environmental Modelling and Software 2019 Vol. 116 P. 7-25
Urban greenery such as trees can effectively reduce air pollution in a natural and eco-friendly way. However, how to spatially locate and arrange greenery in an optimal way remains as a challenging task. We developed an agent-based model of air pollution dynamics to support the optimal allocation and configuration of tree clusters in a city. The Pareto ...
Added: February 24, 2019
, , Bernoulli: a journal of mathematical statistics and probability 2013 Vol. 19 No. 4 P. 1268-1293
Motivated by a problem arising when analysing data from quarantine searches, we explore properties of distributions of sums of independent means of independent lattice-valued random variables. The aim is to determine the extent to which approximations to those sums require continuity corrections. We show that, in cases where there are only two different means, the ...
Added: September 29, 2014
, Journal of Applied and Industrial Mathematics 2020 Vol. 14 No. 4 P. 706-721
The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...
Added: January 30, 2021
P. : Université Paris 13 - Paris Sorbonne Cité, 2013
In this workshop we will bring together participants who have solutions for one or more of the following problems: How can mutual understanding be optimized with the help of technology in hospitals where both patients and professionals have varying language skills, cultural backgrounds and cognitive capacities? Can domain ontologies, natural language processing tools, multilingual knowledge-based ...
Added: December 18, 2014
, , Дискретный анализ и исследование операций 2008 Т. 15 № 1 С. 3-10
Доказывается полиномиальная разрешимость задачи о независимом множестве для бесконечного семейства подмножеств класса планарных графов. ...
Added: August 31, 2012
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Added: February 13, 2013
The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
, Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...
Added: April 7, 2014
, , et al., International Journal of Applied Mechanics 2016 Vol. 8 No. 2 P. 1650016-01-1650016-18
We present a method for evaluating elastic properties of a composite material produced by molding a resin filled with short elastic fibers. A flow of the filled resin is simulated numerically using a mesh-free method. After that, assuming that spatial distribution and orientation of fibers are not significantly changed during polymerization, effective elastic moduli of ...
Added: May 22, 2016
, Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
, , Risk Analysis: An International Journal 2013 Vol. 33 No. 12 P. 2142-2153
We propose a new modeling approach for inspection data that provides a more useful interpretation of the patterns of detections of invasive pests, using cargo inspection as a motivating example. Methods that are currently in use generally classify shipments according to their likelihood of carrying biosecurity risk material, given available historical and contextual data. Ideally, ...
Added: September 29, 2014
Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs
, , et al., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Added: January 27, 2014
Совершенствование преподавания дисциплин математического цикла на основе инвариантов, необходимых для преподавания курса «Эконометрика» экономистам-бакалаврам
, , Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189
The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...
Added: January 28, 2020
Fast reconfiguration of high frequency brain networks in response to surprising changes in auditory input
, , et al., Journal of Neurophysiology (США) 2012 Vol. 107 No. 5 P. 1421-1430
How do human brain networks react to dynamic changes in the sensory environment? We measured rapid changes in brain network organization in response to brief, discrete, salient auditory stimuli. We estimated network topology and distance parameters in the immediate central response period, <1 s following auditory presentation of standard tones interspersed with occasional deviant tones ...
Added: October 23, 2014