# Questions tagged [matrix]

The tag has no usage guidance.

32 questions
Filter by
Sorted by
Tagged with
41 views

### Calculate boolean matrix multiplication (BMM) using transitive closure

Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$. How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...
33 views

### Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview). Sub-matrix ...
122 views

### Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after ...
32 views

### Find sub-matrix containing the maximum number of elements consisting only of 1's [closed]

I am trying to get help on it here, originally posted first at: https://stackoverflow.com/questions/59446920/find-sub-matrix-containing-the-maximum-number-of-elements-consisting-only-of-1s Basically ...
40 views

### Algorithm to find a all valid matrix permutations [closed]

I have an array of $N^2$ numbers like $a = \{ a_1,a_2, ..., a_{N^2} \}$ where all $a_i < F$ where $F$ is a fixed number. I am looking for all permutations where if I put values in $A$ in order (...
99 views

### Matrix chain multiplication: Greedy approach

some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section. The ...
17 views

### Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
70 views

### Min-plus matrix multiplication implementation

I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication: One method for doing this is to ...
35 views

There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows: Consider the linear system $$\begin{bmatrix} a & b \\ ... 2answers 52 views ### Time complexity of matrix subtraction If I have (I-Z) where I is a 3x3 identity matrix while Z is a 3x3 lower triangular matrix, how many subtractions that I should count from this process? Is it costs K subtractions or (K^2+K)/2 ... 1answer 32 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 ... 1answer 31 views ### How can i solve this problem using recursion? [closed] ... 0answers 16 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? 1answer 109 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 ... 3answers 55 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}, } ... 0answers 76 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 ... 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 ... 0answers 37 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 ... 1answer 27 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 ... 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{bmatrix} x & y \end{bmatrix}^T = A \begin{bmatrix} X & Y & Z \end{bmatrix}^T + b \end{... 1answer 314 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 ... 1answer 78 views ### Looking for algorithm to iterate over matrix I have such a product example: ... 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 ... 0answers 33 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\... 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 ... 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 ... 1answer 27 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. ... 0answers 389 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, ... 1answer 30 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 \oplusrepresents any boolean operation. And we are able to evaluate C... 1answer 80 views ### Matrix multiplication randomised verification - error probability Let s say we have an algorithm that takes as input 3 matrix A,B and C$$ \text{Input} :A,B,C \in Mat(n\times n)\text{Question} :\text{is } A\cdot B=C$$the algorith works as follow ;$$ \...
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. ...