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
0
votes
1answer
20 views

What is the fastest and most elegant way to change a matrix dimension?

I have been writing code for a paper and I'm reading an image in RGB space in OpenCV which means that its read as a 3D matrix (HEIGHT x WIDTH x 3 (RGB) ). I'm reshaping the image into a 2D matrix ( ...
0
votes
0answers
9 views

Why is the weight matrix diagonal in weighted least squares regression?

I was going through the theory for weighted least-squares fitting and I understood its basic underlying concepts, but I couldn't understand why exactly do we keep the weights as a diagonal matrix ...
1
vote
2answers
78 views

Matrix rank only adding single row

I have a dense matrix and a set of rows. I would like to check if adding any single row from the set to the original matrix would make the new matrix rank deficient. Right now I am doing a full LU ...
4
votes
2answers
257 views

Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix: $$ \begin{...
0
votes
0answers
10 views

How do I know how many matrix operations a GPU can do in parallel?

My code projects have relied quite a bit on GPU acceleration. But I work with the GPU not through a low level language like OpenGL, but through a few layers of abstraction, namely GPU.js on top of ...
2
votes
1answer
71 views

Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices

Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes. $$ \...
0
votes
0answers
20 views

Books on scientific computing, efficent NN inference, and matrix multipication

I'm trying to learn more about how inference, matrix multiplication, and scientific computing (primarily with tensors/matrices). I'm not sure what the classics here are or what good sources are. I'm ...
2
votes
0answers
21 views

approximate line segments from array of unsorted points

The polygon above is actually a collection of a lot of black points closely packed together. I want to approximate these black points as straight line segments. The black points are not sorted in any ...
3
votes
0answers
65 views

Is minimising the total number of one entries in binary matrices $CA$ and $C^TB$ NP-HARD?

Given a two rectangular binary matrices $A$ and $B$ with dimensions $c\times a$ and $c \times b$ respectively, does there exist an invertible binary matrix C with dimensions $c \times c$ such that the ...
1
vote
1answer
25 views

How can follow this this guide to construct a graph with matrix/reachability

Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
0
votes
1answer
44 views

In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
1
vote
1answer
33 views

Complexity of class finding selection of entries in matrix

Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, ...
0
votes
1answer
22 views

How to find the square with the highest total sum

I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most. For ...
1
vote
2answers
33 views

How to find rows of matrix that are zero everywhere except for 1 entry?

I am interested in finding the rows of a matrix where all entries are equal to zeros except for one. Example: Given the following matrix: \begin{bmatrix}0 &0 &3 & 8\\ 0 & 4 & 0 ...
0
votes
1answer
232 views

Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking ...
0
votes
0answers
16 views

Are My Answers to This Hamming Code Example Correct?

I have attempted to answer this question on Hamming code but i am very new to it and would appreciate feedback on my answers, Thank you! Question My Answers
0
votes
0answers
44 views

Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
1
vote
1answer
31 views

Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct. Question: What would be the complexity of its inversion? On the ...
1
vote
0answers
33 views

Matrix multiplication over range in $O(n)$

Let $Q$ denote the number of queries. I have a $25 \times 25$ matrix in each cell of an array of size $n$. Let us denote this array by $A$. It's a special matrix, more specifically, all elements are $...
1
vote
1answer
43 views

Is matrix multiplication cheaper than inverse?

In wiki, it is shown that the time complexity of matrix multiplication and matrix inverse is similar. But people always to argue it is easier to do matrix multiplication rather than inverse. Is this ...
1
vote
0answers
27 views

How to predict the time complexity of matrix multiplication and inverse on a GPU?

Nvidia GPU can speed up the matrix manipulation greatly. I want to have a basic idea to predict the consumed time for matrix manipulation. How can I analyze the time complexity of matrix ...
0
votes
0answers
34 views

Matrix chain multiplication using dynamic programming

Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem : The table for min. cost is shown below : Edit : Reference https://www.radford.edu/~nokie/...
1
vote
1answer
53 views

How to shift a matrix by x rows and y columns in the most efficient way?

My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ...
-1
votes
1answer
17 views

Find specific position in matrix

Consider a binary (i.e. over $\{0, 1\}$) matrix $A = (a_{ij})$ of size $n \times n$. It is known that there is exactly one $r \in [1; n]$ such that $a_{rj} = 0$ for all $j \in [1; n]$ and $a_{ir} = 1$ ...
3
votes
1answer
89 views

Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
3
votes
1answer
77 views

Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements

Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer. We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that $\sum_{p, q = 1}^k A_{...
2
votes
1answer
92 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 ...
-1
votes
1answer
35 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 ...
2
votes
1answer
46 views

Probability of terminating in a state in a probabilistic algorithm

Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
5
votes
1answer
254 views

Find if there is matrix that satisfying the following conditions

Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an ...
4
votes
1answer
134 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 ...
0
votes
0answers
31 views

Enumerating special Matrices

Is there an efficient algorithm for enumerating binary $n\times n$ matrices which are such that each row has ๐‘˜ 1's and each column also has ๐‘˜ 1's? Related - https://math.stackexchange.com/questions/...
0
votes
1answer
50 views

Time complexity to find out the number of ways to parenthesize N matrices

I am trying to figure out the $time$ $complexity$ to find out the number of ways we can parenthesize $N$ $matrices$. I have approached this problem as, say if we have $N+1$ matrices then we can ...
2
votes
0answers
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 ...
1
vote
0answers
44 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 (...
3
votes
1answer
159 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 ...
1
vote
0answers
18 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 ...
1
vote
1answer
193 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 ...
3
votes
3answers
165 views

How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2. 0 - dot. 1 - block. 2 - start dot (initial position in the path). I have to create a path from the start dot, that connects all the dots in the matrix and ...
3
votes
0answers
57 views

Assignment problem with symmetric matrix

I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm. We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $...
2
votes
1answer
52 views

Queries on knapsack

Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to ...
1
vote
0answers
15 views

Does integer matrix multiplication with its transpose (A^T)*A have more efficient parallel algorithm than the use of symmetricity?

Integer matrix multiplication with its transpose (A^T)A gives symmetric matrix, so, only one half of it should be computed. Besides, the formula for the resulting element rik=Sum[aijajk, j] reduces to ...
1
vote
3answers
161 views

How much can matrix multiplication algorithm be parallelized?

You all may know that simple Matrix Multiplication algorithm: ...
2
votes
1answer
90 views

Numerical issues in solving linear systems

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 ...
0
votes
0answers
72 views

How to solve this dynamic programming puzzle on matrix?

We are given 4 integers N,M ,Q and Z. Initially,the matrix has all zeroes in it. We have to perform Q operations on the matrix. In each operation, any cell of the matrix can be selected(same cell ...
-1
votes
2answers
83 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 ...
1
vote
2answers
72 views

How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
1
vote
0answers
20 views

Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
1
vote
1answer
35 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 ...

1
2 3 4 5