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

181 questions
Filter by
Sorted by
Tagged with
13 views

### Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
23 views

### Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
46 views

### How to cover given entries in a matrix with minimum number of rows and columns?

We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates. example 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 ...
59 views

### In-place matrix transposition using rotations

Some time ago I invented an algorithm for in-place matrix transposition using rotations. A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage ...
73 views

### Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
155 views

### Is order of matrix multiplication affecting numerical accuracy of the result?

I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1). Is ...
31 views

### Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
23 views

### Finding fixed size submatrix with highest sum

I have a matrix, which has N rows and M columns. I need to find n rows and m columns, which has the highest sum. Matrix consists of positive numbers. Not optimal solutions are ok. For example N=M=4; n=...
267 views

### Algorithms for 2-colouring a 2 x N matrix

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...
65 views

### Finding the shortest path for synchronized pawns in a maze

I have been trying to wrap my head around this problem, and I just can't get it. We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
45 views

### The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix

Let us define a $n \times 2$ matrix M consisting of integer sets, such that the first column consists of the so-called intersecting sets, and the second column ...
63 views

### Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
89 views

### Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with $1\le R,C\le 100$, $1\le H\le R$, $1\le W\le C$, an $R\times C$-matrix $L$ and an $H\times W$-...
39 views

### Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
96 views

### Image convolution - image darkens

I'm using kernel convolution in python to blur an image, but in addition to blurring it also turns the image darker. Could someone explain why it happens? ...
173 views

### Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k}$, for example, ...
193 views

### Find an element in sorted 2D-array (matrix)

Given an $N\times N$ array, where elements are decreasing in every row and every column. What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it ...
72 views

### Determinant computation is equivalent to matrix powering

It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation. https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf Does anybody ...
43 views

### Minimum number queries on matrix

As part of a solution to an earlier question, I am interested in the following problem. I have a 2-D matrix $M$. I want to preprocess it in linear time so that I can answer queries of the following ...
76 views

### Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
42 views

### Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column

I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones, such that in that sublist we have only one $1$ from each row or column.
57 views

### Finding disjoint paths between any number of cell pair marked in nXn matrix

What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix? We will say two paths will not intersect if there there is no cell common between any two ...
68 views

### Matrix Representation for logical gates?

I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
8 views

### Clarification on descending direction in optimization of function

Could someone clarify for me why given $f:\mathbb{R}^n \rightarrow\mathbb{R}$ to optimize an iterative function according to : $p^k=-M\nabla f(x^k)$ for $p^k$ to be descending direction the matrix M ...
27 views

### Equivalent Algorithm with Sharman Morrison inversion

I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code: For $t=1,2,...$ $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$ ...
49 views

### Getting N top scores from a matrix

I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example: ...
40 views

### Matrix with zero spectral radius

I need an algorithm which generates a random matrix with spectral radius equal zero. The only solution I have so far is to generate two vectors $v,w$, normal onto each other ($v\perp w$), and then ...
33 views

### Counting on a matrix

I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$. If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
54 views

### Coin flipping problem on an $n \times m$ grid

There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly: Flipping a row of coins; Flipping a colomn ...
283 views

60 views

### Matrix multiplication in recurrent neural networks

I was looking at a tutorial for recurrent neural networks in Python, and I have a question in regards to multiplying matrices of different sizes. Specifically, why does S[t] have 100 elements in it? ...
19 views

### Simple Representation of Matrices with the Given Equivalence Relationship

I'm currently working on an algorithm that requires me to come up with unique matrices. Two matrices are considered equivalent if one's rows and columns can be swapped to make it match the other. For ...
458 views

### Strassen Algorithm for Unusal Matrices

The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81). However, this algorithm is applied for the matrices which are ...
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. ...
1k 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 ...
63 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 ...
535 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 ...
72 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 ...
57 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 ...
163 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 ...
306 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$$ ...
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 ...