The triangle-star transformation, intercalate matrices and applications
type: Item
instance of: scholarly article
zbMATH Open document ID: 0977.05082
author: Isidoro Gitler
publication date: 2002-01-08T00:00:00Z
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 57M25
Mathematics Subject Classification ID: 11E25
zbMATH DE Number: 1574506
zbMATH Keywords: delta-wye transformations
zbMATH Keywords: triangle-star transformations
zbMATH Keywords: intercalate matrices
zbMATH Keywords: sum of squares
zbMATH Keywords: survey
zbMATH Keywords: Ising model
zbMATH Keywords: spin models
zbMATH Keywords: knot theory
MaRDI profile type: MaRDI publication profile
title: The triangle-star transformation, intercalate matrices and applications
review text: This survey work shows the interaction between different parts of mathematics and between mathematics and applications by taking as an example the \(\Delta-Y\) transformations and intercalate matrices. The first part is devoted to the \(\Delta-Y\) transformations in graphs. Besides Truemper's proof of the \(\Delta-Y\) reducibility of planar graphs [J. Graph Theory 13, No. 2, 141-147 (1989; Zbl 0677.05020)] a long list of applications is discussed: shortest paths, maximum flows, electric circuits, etc. In particular, the Ising model, and its generalization to spin models in the context of knot theory is considered. The second part is devoted to intercalate matrices. An \((r,s,n)\)-intercalate matrix is an \(r\times s\) matrix with entries in a set of cardinality \(n\) such that (i) each row and each column has no repeated entries, and (ii) each \(2\times 2\) submatrix has either two or four different entries. It is shown, for instance, how, given \(r\) and \(s\), the problem of finding the minimum \(n\) such that there exists an \((r,s,n)\)-intercalate matrix is related to the combinatorial Nullstellensatz of \textit{N. Alon} [Comb. Probab. Comput. 8, No. 1-2, 7-29 (1999; Zbl 0920.05026)]. Applications such as broadcasting and experimental designs are also linked to intercalate matrices. Nevertheless, the most interesting related question is the sum of squares problem, which is the topic of the last part. An \((r,s,n)\)-formula is an equality \((x_1^2+\cdots+x_r^2)(y_1^2+\cdots+y_s^2)=(z_1^2+\cdots+z_n^2)\) where \(x_i\), \(y_j\) are indeterminates and \(z_k=\sum_{i,j}a_{i,j}^kx_iy_j\) with \(a_{i,j}^k\) integers. The problems considered are: (1) to find the minimum \(n\) such that, given \(r\) and \(s\), an \((r,s,n)\)-formula exists, and (2) to find the maximum \(r\) such that, given \(n\), an \((r,n,n)\)-formula exists. The approach consists in using a correspondence between \((r,s,n)\)-formulae and a class of \((r,s,n)\)-intercalate matrices. The \(\Delta-Y\) tra…
reviewed by: Josep M. Brunat
Recommended article: Q5505230
Recommended article: Matrix transformations of starshaped sequences
Recommended article: An interlacing theorem for tridiagonal matrices
Recommended article: On Starshaped Rearrangement and Applications
Recommended article: A class of transformation matrices and its applications
Recommended article: Regular starlike domains of tridiagonal matrices
Recommended article: Triangularization of Matrices and Polynomial Maps
Recommended article: Matrix Bailey lemma and the star-triangle relation
Recommended article: On semi-star-related matrices
Recommended article: On tridiagonalization of matrices
description: scientific article; zbMATH DE number 1574506