Questions tagged [matrix]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
26 views

Coloring book. Finding region by point

Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D ...
0
votes
0answers
10 views

Complexity of Inserting an element in a sorted matrix [duplicate]

If in a matrix (m*n) having sorted rows and sorted columns then time complexity to insert new element?
1
vote
1answer
56 views

Select K columns from matrix and one element from each row that has maximum sum

Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each ...
1
vote
3answers
48 views

In O(1) get the coordinate i,j of a diagonally ordered matrix

Say you have a matrix like this: [][]int{ {0, 2, 5, 9, 14}, {1, 4, 8, 13, 18}, {3, 7, 12, 17, 21}, {6, 11, 16, 20, 23}, {10, 15, 19, 22, 24}, } ...
4
votes
0answers
74 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 ...
0
votes
0answers
32 views

How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
0
votes
0answers
32 views

Computational Complexity of a Matrix Multiplication

I am computing a matrix multiplication with inverse operation $AB^{-1}C$ $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times o}$. So the inverse operation takes $...
2
votes
1answer
21 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
1
vote
0answers
29 views

Finding the linear mapping between homogeneous coordinates of affine camera

If I have an affine camera with a projection relationship governed by: \begin{equation} \begin{bmatrix} x & y \end{bmatrix}^T = A \begin{bmatrix} X & Y & Z \end{bmatrix}^T + b \end{...
2
votes
1answer
213 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
60 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
30 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
20 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\...
1
vote
1answer
56 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
1k 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
22 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
290 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
26 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
68 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
38 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. ...
2
votes
1answer
844 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 ...