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

192 questions
Filter by
Sorted by
Tagged with
13 views

### Strassen's algorithm on unit vectors?

I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum. ...
2k views

### Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
73 views

### Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
652 views

### The line-covering step in the Hungarian algorithm

I am trying to understand the Hungarian algorithm for the assignment problem. I found this presentation which gives an excellent explanation about the algorithm. However, there is one step I do not ...
79 views

### Find the maximizing row-column matches in a matrix

I have a set of R x C matrices similar to the following (can be much longer): C1 C2 C3 C4 C5 C6 R1 0.32 0.81 NA NA NA NA R2 0.90 -0.44 0.95 ...
95 views

### Advantages (from a mathematical perspective) of representing data as symmetric matrices

From Wikipedia, a symmetric matrix is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing ...
190 views

### Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size. For example if ...
348 views

### How does matrix chain multiplication problem has an optimal substructure?

We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure? For eg. consider if ...
71 views

### Efficiently compute parallel matrix-vector product for block vectors with FFTs?

Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product $$w = (E\otimes I_N)v$$ ...
50 views

### Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
79 views

### Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
159 views

### Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?

It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
129 views

### Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero

Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero? It is ...
610 views

### Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
86 views

### What is the run time of this algorithm?

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits ...
253 views

### LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
26 views

### Write an algorithm such that if an element in an MxN matrix is 0, its entire row and columns are set to 0 [duplicate]

For this question, I implemented this: ...
517 views

### What is the fastest known algorithm for matrix multiplication as of (2017/11)?

Recently I have learned about both the Strassen algorithm and the Coppersmith–Winograd algorithm (independently), according to the material I've used the latter is the "asymptotically fastest known ...
634 views

### How to prove that matrix inversion is at least as hard as matrix multiplication?

Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
3k views

### Fastest algorithm for matrix inversion

What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)? One way to calculate the inverse is using the gaussian elimination method....
31 views

### What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form? Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations? Technically $O(n^3)$ row ...
89 views

### Which algorithms provide high compression ratios for bit matrices?

I have an x*y bit matrix where the total number of bits fluctuates between ~1,000,000 and ~20,000,000 bits. The rows are much smaller than the columns. An example matrix might be of size 1,000,000 x ...
52 views

### Does the specific size of matrices affect the performance of matrix operations?

I was reading DeepMind's paper on I2A's and realized that the sizes of the hidden layers in their model were all like 32, 64, 256, and so on: all powers of 2. I have found the same thing in other ...
512 views

### Lower Bound of Matrix Multiplication

I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani The authors state in page $67$: The preceding formula implies an $O(n^3)$ algorithm for matrix ...
45 views

### How many iterations of Lanczos bidiagonalization are required in order to obtain the first k singular values/vectors of a matrix?

I am trying to implement a fast SVD algorithm for obtaining the first $k$ singular values/vectors of an $M\times N$ matrix ($k < \min(M,N)$) using the following 2-step process: 1) bidiagonalize ...
103 views

### Finding maximum rectangular frame in array of zeros and ones

I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any ...
28 views

### Hebbian rule doesn't get to a fixpoint

I'm trying to implement an Hopfield Network for pictures of 32x32 bits either 1 or -1; I have these 3 pictures and I transform each of them in a vector of 1024 elements. Then I take the 3 vectors and ...
46 views

### Algorithm for finding a matrix which satisfies certain constraints [closed]

Given a list of entries entryList, determine a 4x4 matrix of which you sum up the entries specified in entryList such that there ...
136 views

### Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic

Given an array of $n^2$ integers, what is the most efficient way to determine whether any permutation of those integers can form a magic square? "Magic square" being an arrangement of those integers ...
505 views

### Complexity of multiplying matrix

Let's consider the following algorithm to multiply squares matrix: A is a matrix of NxN. ...
43 views

757 views

729 views

### Suitable choice for moderate-size square matrix multiplication?

The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, ...
625 views

### Running time of sparse matrix multiplication

Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
175 views

### Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$

How many matrices satisfy the following constraints? $n$ rows $n$ columns Cell values are either $0$ or $1$ Sum of any row is at most $m$ sum of any column is at most $m$ Is there a formula or an ...