I am looking for a python code to create a 5 by 5 zero-one matrix with determinant equal to 5. (Such a matrix does exist but it is a consequence of some mathematical theorems. I like to try to find an actual example of such matrix using computer)
Creating a simple search code is time consuming (at least for my little pc!) because there are 2^(25) 5 by 5 zero-one matrix.
Consider utilizing a hill-climbing approach:
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 = 10000,
) -> np.ndarray | None:
"""Trys to find a size x size zero-one matrix with a target determinant.
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
size = 5
max_attempts = 10000
result_matrix = find_matrix_with_determinant(target_det,
size=size,
max_attempts=max_attempts)
if result_matrix is not None:
print(f'Found a matrix of size {size} x {size} with determinant {target_det}:\n', result_matrix)
else:
print(f'No matrix size {size} x {size} found with {target_det=} within {max_attempts=}.')
if __name__ == '__main__':
main()
Example output matrix_size = 5:
Found a matrix of size 5 x 5 with determinant 5:
[[0 1 1 1 0]
[1 1 0 0 1]
[0 0 0 1 1]
[1 0 1 1 0]
[0 0 1 0 1]]
Example output with matrix_size = 20:
Found a matrix of size 20 x 20 with determinant 5:
[[1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1]
[1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 1]
[0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1]
[1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1]
[1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1]
[1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1]
[0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0]
[0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1]
[1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0]
[1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1]
[0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1]
[1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0]
[0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1]
[1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1]
[1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0]
[1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0]
[1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1]
[1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 0]
[0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0]
[1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0]]