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
0answers
29 views

Multiplication of Upper triangular matrix and Lower triangular matrix

If I have an Upper triangular matrix A and Lower triangular matrix B, what could be the most efficient algorithm to get AxB and BxA. Also what would be the formula for total number of multiplication ...
0
votes
1answer
23 views

mapping function to map the index of Lower triangular matrix

If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the ...
0
votes
0answers
24 views

How to determine the number of active linearly independent constraints in a basic feasible solution for linear programming?

I am trying to determine if a given solution is a basic feasible solution. I am working with an $n-$dimension polyhedron $P$ defined by a set of $M$ inequalities $Ax \leq B$. I am running into an ...
1
vote
1answer
62 views

Time complexity of computing $AA^T$

What is the time complexity of computing $AA^T$? The context is building a co-citation weighted adjacency matrix.
3
votes
1answer
32 views

Does this algorithm for permuting rows and columns of a matrix converge?

Given a binary matrix, define the magnitude of a row by reading off the numbers in it left to right and similarly for columns, reading the numbers going down. For instance, the row magnitude of the 1-...
1
vote
1answer
80 views

Iterated multiplication of permutation matrices

Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where $m=\mathit{poly}(n)$ $m=\...
2
votes
0answers
64 views

Prove lower bound on boolean circuit

Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$: $ A = \begin{...
1
vote
0answers
37 views

Change a matrix into lower triangular matrix

I have a matrix over integer of size (50,50). I want to know whether it is possible to exchange rows and columns in such a way so that the transformed matrix is a lower triangular whose diagonal ...
2
votes
0answers
50 views

Verifying a matrix is Copositive

A symmetric matrix $A\in \Bbb{R}^{n\times n}$ is copositive if for every vector $x\in\Bbb{R}^n$ with non-negative entries, we have $$x^TAx \ge 0.$$ What are known methods to check if a specific matrix ...
0
votes
1answer
48 views

Inverting an image, as a matrix

I am curious about something pretty simple, though I have never heard, read and more sadly seen any example of it. Take any image, represent it as a matrix, invert the matrix (assuming the inverse ...
2
votes
1answer
37 views

Understanding the coefficient matrix of Hermite Interpolation

I was not sure whether this is a computer science question or a math question, so I posted it here, hope that it is alright. I am trying to learn the technique of Hermite interpolation. I do ...
0
votes
1answer
36 views

Algorithm chalenge: find minimum range to cover all houses with light

N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R? N is an array containing location of each house. K is ...
0
votes
0answers
29 views

The many strengths of Pagerank

PageRank is used and studied in incredibly many contexts. It is taught in many courses worldwide, with several books and thousands of papers devoted to it. To this regard, PageRank plays a quite ...
0
votes
0answers
31 views

Calculate all pairs of outer products between columns in matrix

Imagine you have a matrix m of dimension MxN What I'm trying to do is get a set of elements (of length N*(N-1)/2) of the diagonal elements (each of whose individual length would be M) of the outer ...
1
vote
1answer
35 views

Bit complexity of $n$-th Fibonacci number using matrix multiplication

I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations ...
2
votes
1answer
61 views

Matrix chain multiplication recurrence and its solution

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
0
votes
0answers
19 views

find maximum number of sections that satisfies the condition in a grid

Here is the description of a problem Given an array of strings representing an $N$x$N$ grid of $red$ and $blue$ cells and a target color $r$ or $b$, partition the grid into $N$ sections of $N$ ...
1
vote
0answers
32 views

Find exact sum in path

So the question is Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
0
votes
1answer
88 views

Proving NP-completeness for a not so cheesy problem

Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. ...
1
vote
1answer
111 views

In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity? Hi, I was reading this question but I ...
0
votes
1answer
21 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
19 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
89 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
280 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
12 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
74 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
28 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 ...
2
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
27 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
53 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
34 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
37 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 ...
-1
votes
1answer
2k 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
19 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
34 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
35 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
45 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
40 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
45 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
61 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
107 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
84 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
172 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
36 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
57 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 ...

1
2 3 4 5 6