Decomposing Matrix Values into Two Numbers in a Specified Manner

March 5, 2024

Having this matrix I want to decompose the numerical values (those that are not None), in this case 6, 9, 9, 3, 5, and 4 into 2 numbers that added together give those numbers.

matrix_aux = [
[None,    6, None,    9],
[   9, None,    3, None],
[None,    5,    4, None]
]

A combination should be left by placing an additional column in the matrix matrix_aux, and then an additional row, in which a decomposition of the numerical values that were in the original matrix_aux will be made.

A decomposition like this should follow, ensuring that all decompositions respect those already carried out previously. This would be a correct output:

matrix_aux_with_num_decompositions = [
[None,    6, None,    9,    4],
[   9, None,    3, None,    2],
[None,    5,    4, None,    3],

[   7,    2,    1,    5      ]
]

Note that all decompositions respect each other mutually,

decomposed numerical value = row decomposition + column decomposition
6 = 4 + 2
9 = 4 + 5
9 = 2 + 7
3 = 2 + 1
5 = 3 + 2
4 = 3 + 1

To solve this problem, I think you should use a combination of techniques, including backtracking and dynamically updating the array.

# Function to decompose a number into two numbers that sum up to that value
def decompose_number(number, previous_decompositions):
    for i in range(1, number):
        complement = number - i
        if i not in previous_decompositions.values() and complement not in previous_decompositions.values():
            return i, complement

# Find numeric values and their decompositions
decompositions = {}
for row in aux_matrix:
    for element in row:
        if element is not None:
            if element not in decompositions:
                decompositions[element] = decompose_number(element, decompositions)

# Add an additional column to the matrix
for row in aux_matrix:
    row.append(None)

# Add an additional row for decompositions
aux_matrix.append([None] * len(aux_matrix[0]))

# Add values and decompositions to the matrix
for i, row in enumerate(aux_matrix[:-1]):
    for j, element in enumerate(row[:-1]):
        if element is not None:
            row[-1] = decompositions[element][0]
            aux_matrix[-1][j] = decompositions[element][1]

for row in aux_matrix:
    print(row)

I have tried this code but it gives me decompositions that contradict each other, for example here it is saying that 3 = 3 + 1, which does not make sense

[None,    6, None,    9,      1]
[   9, None,    3, None,      1]
[None,    5,    4, None,      1]

[   8,    4,    3,    8,   None]

>Solution :

This problem can be re-phrased as a linear system of equations and then solved with numpy.linalg.solve.

import numpy as np
from copy import copy
from random import randint

matriz_aux = [
[None, 6, None, 9],
[9, None, 3, None],
[None, 5, 4, None],
]

matrix_aux_with_num_decompositions = copy(matriz_aux)

matriz_aux = np.array(matriz_aux)

rows, cols = matriz_aux.shape

seq = np.zeros((rows+cols, rows+cols))

vals = []

# Setup matrix representing system of equations
for i in range(rows):
    for j in range(cols):
        if matriz_aux[i,j]:
            seq[len(vals), i] = 1
            seq[len(vals), rows + j] = 1
            vals.append(matriz_aux[i,j])

# Set arbitrary values so matrix is non-singular
for extra_eq in range(len(vals), rows+cols):
    seq[extra_eq, extra_eq] = 1
    vals.append(randint(0, 100))

dcmp = np.linalg.solve(seq, vals)

for row in range(rows):
    matrix_aux_with_num_decompositions[row].append(dcmp[row])

matrix_aux_with_num_decompositions.append(list(dcmp[rows:]))