Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
32 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 ...
-2
votes
0answers
27 views

What did my teacher tell me in machine learning? [closed]

So my teacher told me something along the lines of dependent and independent matrices related to Android and unpacking Android files to Java ones and checking dependent matrix or something of that ...
1
vote
1answer
32 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 ...
1
vote
1answer
40 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.
0
votes
0answers
17 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 ...
3
votes
1answer
44 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$$ ...
0
votes
0answers
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 ...
0
votes
0answers
25 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$ ...
1
vote
1answer
46 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: ...
1
vote
0answers
18 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 ...
1
vote
0answers
28 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
1answer
49 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 ...
3
votes
1answer
124 views

Minimize Manhattan distance travel algorithm

I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has. Say I have a matrix like: $$ \begin{array}{|r|r|r|} \hline \...
1
vote
1answer
34 views

Could a Van Emde Boas tree be used for storing matrices?

I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix. I was wondering if ...
0
votes
1answer
74 views

Merge sort mxn matrix

The question is as follows: I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct) ...
1
vote
0answers
35 views

Sparse Matrix inversion without actual inversion

I want to know what are the efficient way to invert a Sparse Matrix? Are there any algorithm,linear algebra or expansions that make this task easier with out actually inverting the matrix? Thank you ...
0
votes
1answer
31 views

Rows and columns in quantum-gate matrices read the same - why?

I have noticed that for all the matrices representing quantum gates, if we read rows left-to-right and top to bottom, the read the same as columns top to bottom left to right. Example: \begin{...
0
votes
0answers
711 views

Algorithm (Addition of two matrices)

A file F holds the non-zero elements of two large n×n matrices, A and B. The matrix entries are stored as triplets (i,j,value), where value is the (i,j)th element of a matrix. The file first stores ...
0
votes
1answer
44 views

Compute unknown matrices that minimize a sum

This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|...
0
votes
1answer
31 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? ...
2
votes
1answer
16 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 ...
1
vote
2answers
174 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 ...
2
votes
1answer
12 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. ...
0
votes
1answer
525 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
34 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
224 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
53 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
41 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
109 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
0answers
54 views

Can we raise a $k \times k$ matrix to the $n$th power in $O(\log{n})$?

If we want to raise a a $k \times k$ matrix, $A(k)$, to the $n$th power, we can decompose it into $(A(k)^{n/2})^2$ if $n$ is even, and $A(k)(A(k)^{\frac{n-1}{2}})^2$ if $n$ is odd. Hence, we can solve ...
2
votes
1answer
235 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
68 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
42 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
48 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
132 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
108 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
279 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
75 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
146 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
245 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
342 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 ...
2
votes
1answer
1k 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
30 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
69 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
44 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 ...
2
votes
1answer
251 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
43 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
87 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
25 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 ...