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
1
vote
1answer
18 views

Variation on Matrix Chain problem -- compute diagonal only?

How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square) First computing the matrix product and then ...
0
votes
0answers
44 views

Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
0
votes
1answer
51 views

Prove Permutation approach of finding best paranthesization to matrix chain multiplication is $4^n$

Suppose we have matrices $A_0,⋯,A_{n−1}$ (you can say $n $ matrices). Matrix $A_i$ is with dimension $d_i\times d_{i+1}$. If we would like to find all possible permutations to find the best ...
0
votes
0answers
27 views

Finding sequences in a binary matrix with recursion

Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion? I know how to solve the problem without recursion ...
1
vote
1answer
37 views

What is the space-complexity of the Newton-Raphson algorithm?

What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.
0
votes
1answer
24 views

Lower bound on number of zero columns in matrix

I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which ...
-1
votes
1answer
32 views

how to optimise this

Say you are given a matrix $M (A \cdot B)$ when $A$ is the number of rows and $B$ is the number of columns. Now we are free to pick one element from each column. Lets say these elements are $E = \{ ...
1
vote
0answers
44 views

Sort rows and columns of matrix by permuting

I am trying to sort square matrix of size $N$ by $\textbf{only permuting}$ rows and columns, such that row appear in increasing (left to right) while columns appear in decreasing order (top to bottom)....
0
votes
1answer
24 views

How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?

Suppose, that I have a four-by-four matrix and I want to print each element of it. ...
0
votes
0answers
44 views

Given $n$ sets of matrices, find $n$ matrices that have the least number of LCDs among their entries

Let's say I have $n$ sets of matrices $$ A = \left\{\begin{pmatrix} 2 & 4 & 17\\ 5 & 6 & 9\\ \end{pmatrix} \begin{pmatrix} 2 & 4 & 18\\ 5 & 6 & 9\\ \end{pmatrix} \right\...
1
vote
1answer
34 views

Matrix-vector multiplication using only lower triangular of matrix

Suppose one has a large sparse symmetric positive definite matrix $A$ and wants to multiply it by a vector $x$. Only the lower triangular part of matrix A is stored/known. The multiplication $Ax$ ...
12
votes
3answers
2k views

How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B? This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution ...
1
vote
2answers
101 views

Fast computing of a matrix power for large integer values in C++

I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix. My objective is to compute the power of the squared matrix ...
0
votes
0answers
64 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
31 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
30 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
71 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
43 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
99 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
67 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
39 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
71 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
78 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
45 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
44 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
30 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
32 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
43 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
74 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
23 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
37 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
91 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. ...
2
votes
1answer
194 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
24 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
46 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
106 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
298 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{...
2
votes
1answer
76 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. $$ \...
2
votes
0answers
31 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
66 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
28 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
60 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
36 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
23 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
55 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
3k 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
21 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
1
vote
1answer
40 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
2 3 4 5 6