As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [matrices]

For questions about construction and modification of matrices, objects represented by 2-dimensional arrays that are used to define linear operators within linear algebra.

282 questions
Filter by
Sorted by
Tagged with
56 views

### Selecting a submatrix of a binary matrix NP hard?

I have the following problem and I am wondering if it is NP Hard or not. Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$. A ...
39 views

### How to generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices?

the question is as follows: "Generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices for which n is not necessarily an exact power of 2. Give a recurrence describing its running time. ...
1 vote
152 views

### Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows

I have a matrix (input): -- c1 c2 c3 r1 AA BB CC r2 CC RR BB r3 EE DD FF r4 KK DD EE r5 DD GG KK r6 PP QQ KK Let's call each matrix cell a namespace. If two ...
1 vote
24 views

### Writing an Algorithm to Represent a Bit Matrix in Minimal Operations?

I am trying to come up with an algorithm to find the minimal representation of the transformation from a zero matrix to a target matrix. Specifically, I have an empty matrix and can perform operations ...
19 views

### How to optimize an approximated matrix multiplication?

Suppose the objective I try to maximize is $$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$ where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note ...
1 vote
84 views

### Given a binary matrix, find the number of sub-matrices with all ones

Given a matrix A, let Aij denote the element of the i'th row and j'th column. $$A_{i,j}\in \{0, 1\}$$ Find the number of sub-matrices with all ones. 1 <= #rows, #columns <= 150 P.S. This ...
56 views

### Permuting matrix entries to lower rank

Suppose I have a rank-$k$ matrix $A \in \mathbf{R}^{m \times n}$. Now suppose this matrix has its elements shuffled by an adversary to maximize the rank. Is there a way to reverse this permutation and ...
1 vote
35 views

### Adding two 2D matrices together: row by row vs column by column

When adding two 2D matrices of the same size (in row major format), in sequential code with no vector operations, is it faster to add them column by column or row by row? At first I thought it would ...
2k views

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were ...
191 views