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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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. ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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$$ ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
8
votes
0answers
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 ...
5
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
26 views
-2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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....
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
4
votes
1answer
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 ...
1
vote
2answers
505 views

Complexity of multiplying matrix

Let's consider the following algorithm to multiply squares matrix: A is a matrix of NxN. ...
2
votes
0answers
43 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
2answers
2k views

EXTRACT MIN algorithm for Young tableau

This are two sections from a task I got. The Young tableau is defined as a matrix of m rows on n columns so that the bars in each row are sorted in ascending order Left to right and the ...
3
votes
1answer
273 views

Need clarification about the use of Big-O to describe matrix sparsity

In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around ...
8
votes
3answers
4k views

Fastest way to solve a system of linear equations

I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is ...
2
votes
1answer
729 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 ...
9
votes
2answers
906 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$ ...
3
votes
1answer
712 views

Finding the bandwidth of a band matrix

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the ...
3
votes
1answer
235 views

Count number of linearly independent subsets of columns of a binary matrix

I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly ...
3
votes
1answer
212 views

Cost of solving a matrix equation using the FFT

I am trying to calculate $$V = (H^TH+I)^{-1} U$$ where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. ...
1
vote
0answers
202 views

How to solve linear system with modulus operation?

I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$. ...
3
votes
1answer
277 views

Showing that a binary linear code $C$ is self-dual

Let $C*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ is extended to the word $c_1, c_2, c_3, c_4, c_5, c_6,...
3
votes
1answer
757 views

Decoding a binary linear code given its generator matrix

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
5
votes
1answer
1k views

How can I restructure matrices to have non-zero elements close to the diagonal?

I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members ...
3
votes
1answer
85 views

$(max,+)$ matrix product with limited number of values

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$...
1
vote
1answer
41 views

Pick matrices such that each partial sum is positive

There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g: $\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$ $\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$ ... $\{M_{n,1},M_{n,2},...
3
votes
1answer
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, ...
0
votes
1answer
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$?
5
votes
1answer
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 ...
1
vote
0answers
49 views

How to make a certain matrix in Matlab [closed]

So I'm working on a project and I'm totally stuck right now on how to generate an nxn matrix in Matlab (where n is defined by user input). I need to make a matrix that has ones diagonally, zeroes ...
1
vote
1answer
113 views

Given a binary matrix, how to find the starting coordinates of a sub matrix?

Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from ...