# Matrix Convolution

Implement convolution of a matrix.

Convolution is the process of adding each element of the image to its local neighbors, weighted by the kernel. In other words, this is an element-wise product by the kernel on the sub-matrix, followed by a summation.![](/files/-LoJIfSpPNuFPWcphMKs)

**Complexity:** O(k1\*k2\*m1\*m2) time where k are the dimensions of the kernel and m are the dimensions of the matrix.

```python
import numpy as np

# kernel (2n+1) by (2n+1) for all natural numbers
# that does not exceed dimensions of matrix
def convolution(matrix, kernel):
    m_rows = matrix.shape[0]
    m_cols = matrix.shape[1]

    k_rows = kernel.shape[0]
    k_cols = kernel.shape[1]

    assert (k_rows <= m_rows and k_cols <= m_cols)
    assert (k_rows % 2 != 0 and k_cols % 2 != 0)

    convolution = np.zeros((m_rows - int(k_rows / 2) - 1,
                           m_cols - int(k_cols / 2) - 1))

    for i in range(0, len(convolution)):
        for j in range(0, len(convolution[0])):
            submatrix = matrix[i:k_rows + i, j:k_cols + j]
            element_wise_mult = np.multiply(submatrix, kernel)
            convolution[i][j] = round(np.sum(element_wise_mult))

    return convolution


matrix = np.matrix('35 40 41 45 50; 40 40 42 46 52; 42 46 50 55 55; 48 52 56 58 60; 56 60 65 70 75')
kernel = np.matrix('0 1 0; 0 0 0; 0 0 0')
print(convolution(matrix, kernel))

matrix = np.matrix('17 24 1 8 15; 23 5 7 14 16; 4 6 13 20 22; 10 12 19 21 3; 11 18 25 2 9')
kernel = np.matrix('8 1 6; 3 5 7; 4 9 2]')
print(convolution(matrix, kernel))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/array-and-strings/matrix-convolution.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.