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
2 answers
45 views

Counting the number of parenthesization

I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says: Denote the number of ...
user avatar
1 vote
1 answer
28 views

Complexity of finding $d$ largest eigenvectors of a symmetric matrix

I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
user avatar
0 votes
2 answers
50 views

What kind of algorithm do i need when the place of numbers changing according to n number?

I have a project in Golang. But i don't have any idea about how to solve it. n will be an odd number (Feedback will be given if an odd number is not written) As output, a structure with n*n matrix ...
user avatar
1 vote
0 answers
20 views

Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
user avatar
0 votes
0 answers
11 views

runtime of solving matrix differential equation wrt dimensions of matrix

Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is Does time-...
user avatar
3 votes
0 answers
49 views

Low-rank matrix completion is NP-hard

In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
user avatar
1 vote
1 answer
17 views

Find indices of equal cells in a matrix

I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example: $ \begin{...
user avatar
4 votes
1 answer
121 views

Maximum sum of values in a square grid (one in each row/ column)

this is my first post here so bare with me :). What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from ...
user avatar
  • 41
1 vote
0 answers
34 views

Time complexity of computing general imminant

Consider the immanent of $n \times n$ complex matrices \begin{equation} \operatorname{Imm}_f(A) = \sum_{\sigma \in S_n} f_n(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}. \end{equation} Here $f_n:\pi ...
user avatar
0 votes
3 answers
87 views

Data structure to efficiently add zero-rows to a sparse matrix

I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$). The matrix should support the following ...
user avatar
1 vote
0 answers
43 views

Describing the subproblem graph for matrix-chain multiplication

From Introduction to Algorithms by CLRS: 15.2-4 Describe the subproblem graph for matrix-chain multiplication with an input chain of length n. How many vertices does it have? How many edges does it ...
user avatar
4 votes
0 answers
61 views

minimizing a pairwise sum with respect to a sequence of integers

Let $m$ and $n$ be two integers, where $m \leq n$. Suppose you are given $m^2$ matrices $W^{i,j} \in \mathbb{R}^{n \times n}$ for $i, j \in \{1, \dots, m\}$. The goal is to find a sequence $a$ of $m$ ...
user avatar
  • 445
7 votes
1 answer
574 views

Optimizing a sum of matrix chains

Edit Jan 31: important special case is when the sums form a nested structure, search for "Hasse diagram is a tree" below Here's a practically relevant variation on matrix chain problem: Find ...
user avatar
4 votes
2 answers
78 views

Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?

I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result (see ...
user avatar
  • 5,144
8 votes
11 answers
4k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
user avatar
2 votes
0 answers
81 views

Is it NP-hard to find different roots of different matrices simultaneously?

Consider the following problem: input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$. output: a ...
user avatar
  • 21
1 vote
1 answer
51 views

A hash function for a 2D hash table with a scattering property?

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
user avatar
  • 11
6 votes
1 answer
121 views

Computing tr(ABCD...)

Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, ...
user avatar
2 votes
1 answer
63 views

Cover 2 by n binary matrix with submatrices of minimum total size

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
user avatar
  • 115
3 votes
1 answer
66 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
user avatar
3 votes
2 answers
201 views

Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...
user avatar
1 vote
1 answer
35 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 ...
user avatar
0 votes
0 answers
70 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 ...
user avatar
0 votes
1 answer
54 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 ...
user avatar
  • 459
0 votes
0 answers
35 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 ...
user avatar
  • 115
1 vote
1 answer
52 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.
user avatar
  • 113
0 votes
1 answer
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 ...
user avatar
  • 31
-1 votes
1 answer
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 = \{ ...
user avatar
  • 201
1 vote
0 answers
51 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)....
user avatar
0 votes
1 answer
151 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. ...
user avatar
0 votes
0 answers
45 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\...
user avatar
1 vote
1 answer
111 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$ ...
user avatar
  • 11
12 votes
3 answers
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 ...
user avatar
  • 157
1 vote
2 answers
155 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 ...
user avatar
0 votes
1 answer
56 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 ...
user avatar
0 votes
0 answers
74 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 ...
user avatar
1 vote
1 answer
116 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.
user avatar
3 votes
1 answer
70 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-...
user avatar
  • 55
1 vote
1 answer
110 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=\...
user avatar
2 votes
0 answers
71 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{...
user avatar
1 vote
0 answers
49 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 ...
user avatar
  • 33
2 votes
0 answers
83 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 ...
user avatar
0 votes
1 answer
146 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 ...
user avatar
  • 121
2 votes
1 answer
81 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 ...
user avatar
0 votes
1 answer
53 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 ...
user avatar
  • 133
0 votes
0 answers
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 ...
user avatar
  • 1
1 vote
1 answer
64 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 ...
user avatar
  • 13
2 votes
1 answer
137 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 ...
user avatar
0 votes
0 answers
18 views

How to do initialization of vector for an algorithm in MATLAB?

...
user avatar
0 votes
0 answers
27 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$ ...
user avatar
  • 125

1
2 3 4 5 6