# 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.

306 questions
Filter by
Sorted by
Tagged with
23 views

### Kronecker Decomposition Algorithm

I am looking for an algorithm that decomposes a $2^n$ square matrix into a Kronecker product $\otimes$ of $n$ number of $2 \times 2$ matrices. Does anyone know if there is an implementation out there ...
89 views

### Is this "binary submatrix sum equation" problem NP-hard?

There is an unknown matrix $A$ of $R$ rows and $C$ columns. The entry at the $r$-th row, $c$-th column is $A_{rc}$. The matrix is a binary matrix, i.e. each entry is either 0 or 1. Another matrix $B$ ...
• 488
1 vote
29 views

### Extract dominant value per column with single value per row in a matrix

Given a matrix $A \in \mathbb{R}_{+}^{n \times m}$ where $m \geq n$. I want to convert it into a form where there is a single $1$ per row yet no more than a single $1$ per column. The logic is convert ...
• 13
52 views

### How do you remember the algorithm for rotating a square matrix?

The algorithm for rotating a square matrix 90 degrees is neat, and it is documented here and here. However, it is difficult to remember, and requires one to look it up first in order to implement it. ...
• 173
1 vote
2k views

### Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
31 views

### Complexity of strong graph realization problem

Given a simple graph $G$, let $k^{th}$ degree of a vertex $v_i\in G$ denote the number of vertices that have distance $k$ from $v$. Notice that first degree is equivalent to degree by standard ...
• 1,736
30 views

### Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M$ such that the rank of the matrix $$A = \sum_{m \in N}m$$ is minimal. I am wondering if anyone have seen ...
• 225
19 views

### What is "broadcasting"?

Is "broadcasting" in the context of tensors, vectors, and matrices a mathematical term, or one only used in computer engineering? Who coined this term?
• 154
1 vote
23 views

### Algorithm for solving linear equations if interested only in the first component

If I want to solve $\mathbf A \mathbf x = \mathbf b$, but I am only interested in the value of $x_1$, what algorithm should I use, and will it always be strictly more efficient than solving for all of ...
39 views

### Recursive grid search of a sorted matrix

I have an algorithm that is checking whether the given key is present in the 2D sorted array where each row is sorted in an ascending order from left to right and ...
• 1
38 views

### Is there a way to confirm a matrix multiplication solution in O(n)

Let A, B matrices of dimensions $\sqrt{n} * \sqrt{n}$ So that each has a total of n elements. Let there be a matrix C. Is there a known way to confirm wether C is the product of the two or not, in O(n)...
• 11
75 views

### Conditional Maximization of a Binary Matrix

Given an $L \times N$ matrix $A$ with only binary values, $A_{ij} \in \{0, 1\}$, and a vector $b$ with $b_j = 2^{j-1}$, I want to find a matrix $\tilde{A}$ that maximizes $\tilde{c}=\tilde{A}b$, ...
• 61
1 vote
41 views

### Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
1 vote
30 views

• 139
83 views

### What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
• 356
79 views

### A version of Bareiss algorithm or similar for symmetric matrices

A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
1 vote
40 views

### Algorithm for the inversion of a striped matrix with tridiagonal stripes

I'd like to compute the inverse of a matrix of size $S^2N \times S^2N$ over complex numbers that is composed of tri-diagonal $S\times S$ size blocks of tri-diagonal $S\times S$ block matrices. This ...
• 11
71 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 ...
• 23
1 vote
161 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
33 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 ...
1 vote
163 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 ...
• 139
65 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
52 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 ...
• 11
3k 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 ...