An approach to solving \(A^{k}=J-I\)
type: Item
instance of: scholarly article
title: An approach to solving \(A^{k}=J-I\)
zbMATH Open document ID: 1032.15011
DOI: 10.1016/S0024-3795(02)00669-9
author: Yaokun Wu
author: Qiao Li
published in: Linear Algebra and its Applications
publication date: 2003-11-19T00:00:00Z
review text: The authors consider the matrix equation \(A^k=J_{d^k+1}-I_{d^k+1}~(*)\) where \(d>1\) is an integer, \(k>0\) is an odd integer, \(J\) is the all-one matrix, \(I\) is the identity matrix, and \(A\) is an unknown \((0,1)\) matrix. The equation (with \(k=3\)) arises from problems concerning digraphs and their walks of length \(3\) connecting two given vertices. The authors conjecture that under the permutation similar equivalence relation there are exactly \(\varphi (k)\) solutions \(A\) to \((*)\) where \(\varphi (k)\) is Euler's totient function (the number of positive integers less than and relatively prime to \(k\)). An approach to verify the conjecture is proposed which establishes a connection between the work on solving the matrix equation \(A^k=J-I\) and the problems of determining the structure of near-\(k\)-factor factorization of cyclic groups and characterizing cycle-powers. Some results are collected about the latter two problems in order to give a better understanding of the approach.
Mathematics Subject Classification ID: 15A24
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 2005976
zbMATH Keywords: matrix equation
zbMATH Keywords: intersection graph
zbMATH Keywords: partitionable graph
zbMATH Keywords: generalized circulant
zbMATH Keywords: near-\(k\)-factor factorization
zbMATH Keywords: row set
zbMATH Keywords: cycle powers
zbMATH Keywords: digraphs
zbMATH Keywords: Euler's totient function
reviewed by: Vladimir P. Kostov
MaRDI profile type: Publication
cites work: Q4484907
cites work: Q2704218
cites work: Q4242951
cites work: Graphical properties related to minimal imperfection
cites work: Graph Classes: A Survey
cites work: Combinatorial designs and related systems
cites work: Combinatorial matrix theory
cites work: Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
cites work: Q3490180
cites work: On the strong perfect graph conjecture
cites work: Star-cutsets and perfect graphs
cites work: Combinatorial designs related to the strong perfect graph conjecture
cites work: Perfect graphs, partitionable graphs and cutsets
cites work: Combinatorial optimization. Packing and covering
cites work: Q3208805
cites work: The Hamiltonian property of consecutive-\(d\) digraphs
cites work: Q5520566
cites work: On stable set polyhedra for K//(1,3)free graphs
cites work: Q3218158
cites work: Q3328583
cites work: On circular critical graphs
cites work: The Polynomial of a Directed Graph
cites work: Directed graphs with unique paths of fixed length
cites work: An Introduction to Symbolic Dynamics and Coding
cites work: Q3320435
cites work: Topics in Intersection Graph Theory
cites work: Q5183521
cites work: Perfect zero–one matrices
cites work: The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
cites work: Some aspects of minimal imperfect graphs
cites work: Circular representation problem on hypergraphs
cites work: Cutsets in perfect and minimal imperfect graphs
cites work: Combinatorial Configurations
cites work: The connectivity of minimal imperfect graphs
cites work: The Strong Perfect Graph Conjecture for Planar Graphs
cites work: Coloring a Family of Circular Arcs
cites work: Q3946199
cites work: Q3478422
cites work: Q3841602
cites work: Q3791271
cites work: On the matrix equation \(A^l+A^{l+k}=J_n\)
cites work: Spectra and elementary cycles of the digraphs with unique paths of fixed length
cites work: On the matrix equation \(A^k=J-I\)
cites work: \(g\)-circulant solutions to the (0,1) matrix equation \(A^m=J_n\)
description: scientific article; zbMATH DE number 2005976