行列式为 5 的 5 x 5 零一矩阵

Question

我正在寻找一个Python代码来创建一个5乘5的零一矩阵，其行列式等于5。（这样的矩阵确实存在，但它是一些数学定理的结果。我喜欢尝试找到一个实际的例子使用计算机生成这样的矩阵）

创建一个简单的搜索代码非常耗时（至少对于我的小电脑来说！），因为有 2^(25) 5 x 5 零一矩阵。

Answer 1

考虑使用爬山方法：

import numpy as np


def generate_initial_matrix(size: int = 5) -> np.ndarray:
  """Generates an initial random matrix with elements 0 or 1.
  Args:
    size: The size of the matrix to generate. Defaults to 5.
  Returns:
    A size x size numpy array with random 0 or 1 entries.
  """
  return np.random.randint(0, 2, size=(size, size))


def tweak_matrix(matrix: np.ndarray) -> np.ndarray:
  """Randomly tweaks a single element in the matrix.
  Args:
    matrix: The matrix to be tweaked.
  Returns:
    A new matrix with one element flipped (0 to 1 or 1 to 0).
  """
  i, j = np.random.randint(0, matrix.shape[0], 2)
  matrix[i, j] = 1 - matrix[i, j]  # Flip between 0 and 1
  return matrix


def find_matrix_with_determinant(
    target_det: int = 5,
    size: int = 5,
    max_attempts: int = 1000,
) -> np.ndarray | None:
  """Trys to find a size x size zero-one matrix with a determinant equal to target_det.
  Args:
    target_det: The target determinant. Defaults to 5.
    size: The size of the matrix. Defaults to 5.
    max_attempts: The maximum number of attempts. Defaults to 10000.
  Returns:
    A size x size np.ndarray with the target determinant or None if not found.
  """
  matrix = generate_initial_matrix(size)
  best_det = np.linalg.det(matrix)
  for _ in range(max_attempts):
    if int(best_det) == target_det:
      return matrix
    new_matrix = tweak_matrix(matrix.copy())
    new_det = np.linalg.det(new_matrix)
    new_matrix_closer = abs(new_det - target_det) < abs(best_det - target_det)
    accept_worse_solution_to_escape_local_minima = np.random.rand() < 0.01
    if new_matrix_closer or accept_worse_solution_to_escape_local_minima:
      matrix, best_det = new_matrix, new_det
  return None


def main() -> None:
  target_det = 5
  max_attempts = 10000
  result_matrix = find_matrix_with_determinant(target_det,
                                               max_attempts=max_attempts)
  if result_matrix is not None:
    print(f'Found a matrix with determinant {target_det}:\n', result_matrix)
  else:
    print(f'No matrix found with {target_det=} within {max_attempts=}.')


if __name__ == '__main__':
  main()

示例输出：

Found a matrix with determinant 5:
 [[0 1 1 1 1]
 [1 0 1 1 1]
 [1 1 0 0 1]
 [1 1 1 0 0]
 [1 1 0 1 0]]