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.
23
questions
9
votes
2
answers
1k
views
Counting islands in Boolean matrices
Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
7
votes
1
answer
342
views
Matrix covering by squares
I wonder about the following decision problem :
Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$.
Question: is it possible to cover all the ones of the ...
7
votes
3
answers
10k
views
Number of submatrices with a particular sum
Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
1
vote
1
answer
4k
views
Complexity of matrix inverse via Gaussian elimination
I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$.
If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
8
votes
5
answers
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 ...
5
votes
4
answers
855
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 ...
5
votes
1
answer
230
views
Is matrix "adjoint-squaring" faster than general matrix multiplication?
The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
4
votes
1
answer
1k
views
Absorbing Markov Chains: An efficient algorithmic approach
Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows:
Given the ...
3
votes
1
answer
7k
views
Strassen's matrix multiplication algorithm when $n$ is not a power of 2
The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
The algorithm multiplies two square ...
3
votes
1
answer
7k
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....
3
votes
1
answer
2k
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 ...
3
votes
2
answers
480
views
Algorithm: Dimension increase in 1D representation of Square Matrix
Consider the matrix with dimension $m \times m$:
$$
M =
\begin{array}{cc}
1 & 1 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
$$
Its 1-D representation:
$$ M^* = \begin{array}...
3
votes
1
answer
380
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, ...
3
votes
1
answer
490
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 ...
2
votes
1
answer
833
views
Lexicographically smallest down-right path in matrix
Here is the problem which I thought was simple dynamic programming, which is however not the case.
Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
2
votes
0
answers
57
views
mx2m modulo-3 matrix solution
Is there an efficient algorithm for the following problem?
Given: a $m$-vector $b \in \{0,1,2\}^m$, and a $m \times 2m$ matrix $A$, with the promise that for every $b' \in \{0,1,2\}^m$, there exists $...
1
vote
2
answers
146
views
Convert lower-left matrix triangle 1D index to row, column
How can I convert a 1D index in the lower-left triangle of a grid into a row and column?
For example, consider this table of 1D indices, indexed by row and column
...
1
vote
1
answer
1k
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 ...
1
vote
1
answer
85
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 ...
1
vote
1
answer
303
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 ...
0
votes
0
answers
111
views
How to solve this dynamic programming puzzle on matrix?
We are given 4 integers N,M ,Q and Z.
Initially,the matrix has all zeroes in it.
We have to perform Q operations on the matrix.
In each operation, any cell of the matrix can be selected(same cell ...
0
votes
1
answer
334
views
mapping function to map the index of Lower triangular matrix
If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the ...
0
votes
0
answers
183
views
Count submatrices with only zeros for each element of the matrix
Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...