Stack Exchange Network

Stack Exchange network consists of 175 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 [matrix]

The tag has no usage guidance.

2
votes
1answer
50 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 ...
1
vote
1answer
31 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
0
votes
0answers
25 views

Computing $A^{-2}BA^{-3}b$

Let $A,B$ be matrices of $\mathbb{R}^n$ space and $b \in \mathbb{R}^n$. Describe a fast algorithm to compute $A^{-2}BA^{-3}b$. How many computations will the algorithm make? This is an exam question ...
1
vote
1answer
29 views

Expectation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $. I need to ...
1
vote
0answers
17 views

Partitioning the columns of a matrix

I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here: Suppose you have a matrix $A\in\...
0
votes
1answer
53 views

Replace 1's with -1's and vice versa in a matix

Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an ...
8
votes
3answers
987 views

Strassen algorithm for matrix multiplication complexity analysis

I see everywhere that the recursive equation for the complexity of Strassen alg is: $$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me. The parameter $n$ is supposed to be the size of the ...
0
votes
1answer
15 views

How to count stores in cache analysis of matrix multiplication

I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out. For ijk iteration, my slides say that there are 2 loads and 0 stores. ...
0
votes
0answers
80 views

Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times

A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s. for eg, n=3, m=3, ...
2
votes
1answer
17 views

What's the connection between the two “Fast Walsh Transform”?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
0
votes
1answer
46 views

Verify Matrix multiplication

Let s say we have an algorithm that takes as input 3 matrix A,B and C $$ Input :A,B,C \in Mat(n\times n)$$ $$Question :\text{is } A*B=C$$ the algorith works as follow ; $$ \text{if }(A*B)_{ij}=C_{...
0
votes
0answers
28 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. ...
1
vote
1answer
247 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 ...