Interpolation between bases and the shuffle exchange network

DOI10.1016/S0195-6698(89)80030-7MaRDI QIDQ1114665zbMATH OpenOpenAlexFDO

Authors Michael Tarsi, Nathan Linial

Publication date 1989

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0195-6698(89)80030-7

zbMATH Keywords

bases of a vector spacefree Boolean algebraswitching network theory

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Applications of graph theory to circuits and networks (94C15)

Review text

Let \(u_ 1,...,u_ n\) and \(v_ 1,...,v_ n\) be bases of a vector space (the interesting case, when the underlying field is finite). Then there exist vectors \(w_ 1,...,w_{n-1}\) such that every n consecutive vectors in the sequence \(u_ 1,...,u_ n\), \(w_ 1,...,w_{n-1},v_ 1,...,v_ n\) form a basis. Similar statements hold in structures other then vector spaces. The case of a free Boolean algebra is shown to be equivalent to an open problem in switching network theory.

Recommendations

• scientific article; zbMATH DE number 3930907
• On the rearrangeability of shuffle-exchange networks
• scientific article; zbMATH DE number 5252182
• scientific article; zbMATH DE number 4063007
• Network interpolation
• An Efficient Algorithm for Generating Linear Transformations in a Shuffle-Exchange Network
• A note on interpolating bases
• Binary shuffle bases for quasi-symmetric functions
• On the method of interchanging networks for permutation problems

Cites work

• Automorphisms of a Free Associative Algebra of Rank 2. II
• Automorphisms of a Free Associative Algebra of Rank 2.I
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 3225079 (Why is no real title available?)
• scientific article; zbMATH DE number 3401090 (Why is no real title available?)
• Notes on Shuffle/Exchange-Type Switching Networks
• Parallel Processing with the Perfect Shuffle
• The Frobenius number and partitions of a finite vector space
• The Universality of the Shuffle-Exchange Network
• Ultracomputers

Cited in

(3)

• A method of batching conflict routings in shuffle-exchange networks
• A lower bound for sorting networks based on the shuffle permutation
• Rearrangeability of bit permutation networks

This page was built for publication: Interpolation between bases and the shuffle exchange network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114665)