布尔矩阵平方根的一些性质

Some Properties of Square Roots for a Boolean Matrix

布尔矩阵的平方根问题是一个到目前为止尚未解决的组合问题.既没有一个通用的准则可以用来判断一个布尔矩阵是否有平方根,对于有平方根的布尔矩阵也没有一种快速的方法构造出其平方根.从布尔矩阵的结构特征出发,首先讨论有平方根的布尔矩阵具有的一些性质,指出布尔矩阵与其平方根在结构上存在的内在联系;基于这些联系,给出两种由已知平方根构造新平方根的方法;最后得到布尔矩阵存在平方根的一个充要条件,并以此给出一种构造布尔矩阵平方根的方法.

The problem of finding square roots for a Boolean matrix is one of the classic unsolved problems of combinatorial optimization.Up to now,there has neither method to judge whether a given Boolean matrix has or not square roots,nor method to construct efficiently the square roots of a given Boolean matrix which has square roots.In this paper,at first,some properties of a Boolean matrix which has square roots are given,some intrinsic relations of the Boolean matrix and its square roots are discovered.Then two methods are obtained to construct new square roots based on a given square root.At the end,a necessary and sufficient condition that a Boolean matrix has square roots is given.