Límites inferiores para el rango de una matriz con ceros y unos fuera de la diagonal principal

Hemos encontrado un límite inferior en el rango de una matriz cuadrada, donde cada entrada en la diagonal principal no es ni cero ni uno, pero cada entrada fuera de la diagonal principal es cero o uno. El rango de tal matriz es al menos la mitad del orden de la matriz. Bajo una condición adicional, el límite inferior es uno más alto. Esta condición significa que algún sistema auxiliar de ecuaciones lineales no tiene solución binaria. Se dan ejemplos que muestran la alcanzabilidad del límite inferior. Este límite inferior en el rango nos permite reducir el problema de encontrar una solución binaria a un sistema de ecuaciones lineales, donde el número de ecuaciones linealmente independientes es suficientemente grande, a un problema similar en un menor número de variables. Se encuentran restricciones sobre la existencia de un gran conjunto de soluciones, cada una de las cuales difiere de una binaria por el valor de una variable. Además, discutimos la posibilidad de certificar la ausencia de una solución binaria para un sistema de un gran conjunto de ecuaciones algebraicas lineales. También se dan estimaciones del tiempo de ejecución para calcular el rango de una matriz con el sistema de álgebra computacional SymPy. Se muestra que el rango de la matriz sobre el campo de residuos módulo un número primo se calcula en menos tiempo del que normalmente se requiere para calcular el rango de una matriz del mismo orden sobre el campo de los números racionales.